题解 P1719 【最大加权矩形】
引子：
给出一段序列，选出其中连续且非空的一段使得这段和最大。
第一行是一个正整数N，表示了序列的长度。(N<=200000)这是 P1115最大子段和 的描述，也就是本题的一维版本。
DP方程：dp[i]=max(dp[i-1]+tmp,tmp) tmp表示这个数列的第i项。代码：
#include<bits/stdc++.h>
using namespace std;
inline int maxn(int a,int b){return a>b?a:b;}
int main(){
int ans=-999999,tmp,i,n,dp[200100]={0};//假装ans是负无穷
scanf("%d",&n);
for(i=1;i<=n;++i){
scanf("%d",&tmp);
dp[i]=maxn(dp[i-1]+tmp,tmp);
ans=maxn(ans,dp[i]);//动态规划
}
printf("%d\n",ans);
return 0;
}那么我们如何来处理这一题呢？
我们可以考虑将矩形压缩成一维，比如处理一个2行的矩形时，将a [ i ][ j ]与a [ i - 1 ][ j ]相加，成为一个新的数组f [ n ]，再使用上述代码进行动态规划，找出局部最优解。
那如何来快速将矩形折叠呢？
我们可以选择前缀和
简单来说，就是在输入的时候，再次加上a[ i - 1 ][ j ]，这样可以用减法来快速表示压缩的矩形。
具体代码如下：
scanf("%d",&n);
int i,j;
for(i=1;i<=n;++i){
for(j=1;j<=n;++j){
scanf("%d",&a[i][j]);
a[i][j]+=a[i-1][j];//根据前缀和定义处理
}
}用样例来表示，输入的是：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2在经过前缀和处理之后，输出的是这个：
0 -2 -7 0
9 0 -13 2
5 1 -17 3
4 9 -17 1可以模拟一下，a[ i ][ j ] - a[ i - k ][ j ]正好是以i为最下面一行，往上k行的压缩结果，这就很方便地表示了压缩后的矩形。
那又怎么循环找出各行为最下一行，不同行数的矩阵最大值呢？
我用i表示以i为最下一行，k表示向上k行，代码如下:
for(i=1;i<=n;++i){
for(k=1;k<=i;++k){
}
}k<=i，保证了i-k>=0。
那再次循环，运用第一个代码的简单变形，可以求出以i为最下一行，向上k行的矩形最大值，多次更新ans，愉快AC。
最后上一下总代吗：
#include<bits/stdc++.h>
using namespace std;
int ans,a[150][150],n;
int maxn(int a,int b){return a>b?a:b;}
//自定义求最大值
int main(){
scanf("%d",&n);
int i,j,k;
for(i=1;i<=n;++i){
for(j=1;j<=n;++j){
scanf("%d",&a[i][j]);
a[i][j]+=a[i-1][j];
}
}//如上，前缀和处理
for(i=1;i<=n;++i){
for(k=1;k<=i;++k){
int f[150]={0},dp[150]={0};//f[j]表示压缩的矩形第j列的值
for(j=1;j<=n;++j){ //其实可以不开数组，一个f就可以
f[j]=a[i][j]-a[i-k][j];//求压缩的矩形第j列的值
dp[j]=maxn(dp[j-1]+f[j],f[j]);//动态规划
ans=maxn(ans,dp[j]);//更新答案
}
}
}
cout<<ans<<endl;//愉快AC
return 0;
}