hdu1081 DP类最长子段和（二维压缩+前缀和数组/树状数组计数）

浏览数：30 / 时间：2015年06月08日

题意：给出一个 n * n 的数字矩阵，问最大子矩阵和是多少。

由于和最长子段和问题类似，一开始想到的就是 DP ，一开始我准备用两个循环进行 DP ，对于每一个（i，j），考察（i - 1，j）与（i，j - 1）， dp 值代表以该点为右下角的最大矩阵和，同时记录下这个矩阵的左上角坐标，状态转移时通过将原和最大矩阵通过补边推到当前和最大矩阵。但是其实这种做法有一个明显的问题，就是转移时，补上边后 dp 值相同怎么办，dp 值相同而矩阵不同的话会影响到下一次状态转移后补上的矩阵的情况，从而影响到下一个矩阵的判断。

并想不出怎么做的我无奈看了题解……二维压缩，好吧，并不懂那是个什么……细看之下才知道，其实就是用数组记录下矩阵后，在 dp 时对于起始结束行不同的矩阵分别 DP ，记录下其中最大值即可。例如对于所有列，考虑其前两行的情况，即子矩阵行数为 2 ，这时每列的两个数可以计算其和为一个数，就能将二维的矩阵转化为一维的数组了，这样再进行与最长子段和相同的操作就能得出答案了。

当然，记录矩阵并且便于计算行之间的和，我用了前缀和数组和树状数组两种方式。这题明显用前缀和数组更加好，因为输入的数不会发生改变，所以前缀和数组更加容易计算，用树状数组做并不是用来体现我的逼格高，只是因为我个人树状数组基本没有在题目中用过几次，所以这次敲一遍训练一下，以免以后遇到了明明会但是敲不出来或者敲得太慢……说白了就是弱……

前缀和数组：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define max(a,b) a>b?a:b
 4 
 5 int t[101][101],dp[101];
 6 
 7 int main(){
 8     int n;
 9     while(scanf("%d",&n)!=EOF&&n!=0){
10         int i,j,k,ans=-0xFFFFFFF,tmp;
11         memset(t,0,sizeof(t));
12         for(i=1;i<=n;i++){
13             for(j=1;j<=n;j++){
14                 scanf("%d",&tmp);
15                 t[j][i]=t[j][i-1]+tmp;
16             }
17         }
18         for(i=0;i<=n-1;i++){
19             for(j=i+1;j<=n;j++){
20                 memset(dp,0,sizeof(dp));
21                 for(k=1;k<=n;k++){
22                     if(dp[k-1]>0){
23                         dp[k]=dp[k-1]+(t[k][j]-t[k][i]);
24                     }
25                     else dp[k]=t[k][j]-t[k][i];
26                     ans=max(ans,dp[k]);
27                 }
28             }
29         }
30         printf("%d\n",ans);
31     }
32     return 0;
33 }

View Code

树状数组：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define max(a,b) a>b?a:b
 4 
 5 int t[101][101],dp[101],n;
 6 
 7 void add(int i,int j,int d){
 8     while(j<=n){
 9         t[i][j]+=d;
10         j+=(j&-j);
11     }
12     return;
13 }
14 
15 int sum(int k,int x){
16     int cnt=0;
17     while(x>0){
18         cnt+=t[k][x];
19         x-=(x&(-x));
20     }
21     return cnt;
22 }
23 
24 int main(){
25     while(scanf("%d",&n)!=EOF&&n!=0){
26         int i,j,k,ans=-0xFFFFFFF,tmp;
27         memset(t,0,sizeof(t));
28         for(i=1;i<=n;i++){
29             for(j=1;j<=n;j++){
30                 scanf("%d",&tmp);
31                 add(i,j,tmp);
32             }
33         }
34         for(i=0;i<=n-1;i++){
35             for(j=i+1;j<=n;j++){
36                 memset(dp,0,sizeof(dp));
37                 for(k=1;k<=n;k++){
38                     tmp=sum(k,j)-sum(k,i);
39                     if(dp[k-1]>0){
40                         dp[k]=dp[k-1]+tmp;
41                     }
42                     else dp[k]=tmp;
43                     ans=max(ans,dp[k]);
44                 }
45             }
46         }
47         printf("%d\n",ans);
48     }
49     return 0;
50 }