Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:鄙视暴力!!其实我也16MS~~DP代码 不准抄袭,

Posted by cyforever at 2010-08-12 17:04:20 on Problem 1050
In Reply To:Re:鄙视暴力!!其实我也16MS~~DP代码 不准抄袭, Posted by:zyx980506 at 2010-03-17 22:32:54
> var i,j,k,x,y,z,n,s,max,x1,y1,x2,y2:longint;
>     a,b:array[0..1000,0..1000]of longint;
> begin
>   readln(n);
>   for i:=1 to n do
>     for j:=1 to n do begin
>       read(a[i,j]);
>       b[i,j]:=b[i,j-1]+a[i,j];
>     end;
>   max:=0;
>   for i:=1 to n do
>     for j:=i to n do begin
>       s:=0;x:=0;
>       for k:=1 to n do begin
>         s:=s+b[k,j]-b[k,i-1];

我用暴力,0ms,212k,ac,方便快捷才是王道。
#include <iostream>

using namespace std;

int main()
{
   int n,i,j,k,m;
   long int max,s,sum;
   int rec[100][100],colsum[101][101]={0};
   long int col[101]={0};

   max=0;
   scanf("%d",&n);
   for(i=0;i<n;i++)
     for(j=0;j<n;j++)
      scanf("%d",&rec[i][j]);

   for(j=0;j<n;j++)
   {s=0;
     for(i=0;i<n;i++)
     {
         s+=rec[i][j];
         colsum[i][j]=s;
     }
   }

   for(i=0;i<n;i++)
     for(j=i;j<n;j++)
     {
         sum=0;
      for(k=0;k<n;k++)
        {
            if(i==0) col[k]=colsum[j][k];
            else col[k]=colsum[j][k]-colsum[i-1][k];
        }
        for(m=0;m<n;m++)
          {
            if(sum<0) sum=0;
            sum+=col[m];
            if(sum>max) max=sum;
          }
        }
     printf("%ld",max);
}
>         if s>max then begin
>           max:=s;
>           x1:=x;x2:=k;
>           y1:=i;y2:=j;
>         end;
>         if s<0 then begin s:=0;x:=k+1;end;
>       end;
>     end;
>   writeln(max);
> end.
> 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator