TIOJ 1122 最大子矩陣 ( 93北市賽 prob 3 )

poao899    -8K    31MS    G++     0.76K     2009-11-14 01:02:26                                 .


很直觀的O(n^3)DP...

是說小乃：O(n^6)爆搜也會過啦



不過DP co起來美觀一點點ˊˇˋ


//****************************

//93 prob 3

#include<stdio.h>
int matrix[22][22];
int sum[22][22],pre,max,n;
main(){
    while(~scanf("%d%d",&n,&matrix[1][1])){
        max=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j==1){
                    if(i!=1)matrix[i][j]=matrix[1][1]+i;
                }
                else{
                    matrix[i][j]=(matrix[i][j-1]*17)%103;
                    if((i+j)%2)matrix[i][j]=-matrix[i][j];
                }
                sum[i][j]=sum[i-1][j]+matrix[i][j];
            }
        }
        for(int top=0;top<n;top++){
            for(int but=top+1;but<=n;but++){
                pre=0;
                for(int i=1;i<=n;i++){
                    if(pre<0){
                        pre=sum[but][i]-sum[top][i];
                        max>?=pre;
                    }
                    else{
                        pre+=sum[but][i]-sum[top][i];
                        max>?=pre;
                    }
                }
            }
        }
        printf("%d\n",max);
    }
}