1050.txt

acm pku 1050题

这个题目很经典的说，O（N^3）的DP。

首先偶们考察这样的题目，简化版：

已知一列数，求任意连续若干个数和的最大值。

SAMPLE： 3 2 -6 2 -1 7

原数3         2       -6        2       -1        7 

处理3         5       -1        2        1        8

因为是连续若干个自然数的和，那么，前面的某个数字取与不取的条件在于：以前面这个数字为结尾的连续数的和最大值是否大于0，如果大于0，那么这个数字必然要会出现在包括数字的序列中，否则无法做到最大。

所以，显然。处理的原则是maxn[i]=max{0,maxn[i-1]}+a[i];

由于无须记录位置。所以，可以直接用一个变量sum代替maxn数组。O(n)的扫描即可。

单列数字的问题解决了，下面我们考察多列数字的

sample:

          0     -2     -7     0 

          9      2     -6     2 

         -4      1     -4     1 

         -1      8      0    -2 



我们可以将多列数字转换成单列数字来做！ 可以这样设想，结果是一个长方形，我们把他压扁，使得宽为1。

引入辅助数组st,st[i][j]代表第i列从第1行开始的数字累加到第j行的值。那么，我们每次压扁的时候，就可以用st[i][j]-st[i][k-1]来表示第i列从第k个数字累加到第j个数字的值。达到压缩的效果。然后用上面单列数字的方法来做。算法时间复杂度O (N^3)


我的代码:

#include <iostream>
using namespace std;

int matrix[102][102];
int cv[102][102];
int mv[102];

int main(){
    int n;
    int lt,ll;
    
    cin>>n;
    for(lt=1;lt<=n;lt++) for(ll=1;ll<=n;ll++) cin>>matrix[lt][ll];
    for(lt=0;lt<=101;lt++) cv[lt][0]=0;
    for(lt=1;lt<=n;lt++) for(ll=1;ll<=n;ll++) cv[lt][ll]=cv[lt][ll-1]+matrix[ll][lt];
    int maxall=0,tmp,sum;
    for(lt=1;lt<=n;lt++){
        for(ll=lt;ll<=n;ll++){
            tmp=cv[1][ll]-cv[1][lt-1];
            sum=tmp;
            for(int kk=2;kk<=n;kk++){
                if(sum>0) sum+=cv[kk][ll]-cv[kk][lt-1];
                else sum=cv[kk][ll]-cv[kk][lt-1];
                if(sum>tmp) tmp=sum;
            }
            if(tmp>maxall) maxall=tmp;
        }
    }
    cout<<maxall<<endl;
    return 0;
}