2015 ACM National Contest Romania G - Por Costel and the Orchard Gym - 100923G （好难的dp）

问题

给一个NxM的矩阵，找一个联通块，让这个联通块的权值最大。
有这么几个要求：
1.每一行不能间断地取点，也就是每一行必须取一段连续的区间。
2.下一行如果取了那么与上一行必须有相交的部分，也就是要联通
3.不能不取，至少取一格
（ 1<=T<=4,1<=n,m<=300 ,-1e4<=a[i][j]<=1e4）

思路

首先，我们很容易想到一个dp
dp[i][j][k]表示到第i行，区间为j-k与上面联通的最大价值。
与区间[j][k]联通也就是上一行左右端点有至少有一个在[j][k]之内
这个代码比较好写，如下

for(int i=2;i<=n;i++){
            for(int j=1;j<=m;j++){
                for(int k=j;k<=m;k++){
                    for(int qq=j;qq<=k;qq++){
                        if(dp[i][j][k]<pre[i-1][qq]+sum[i][k]-sum[i][j-1]){
                            dp[i][j][k]=pre[i-1][qq]+sum[i][k]-sum[i][j-1];
                            pre[i][j]=max(pre[i][j],dp[i][j][k]);
                            suf[i][k]=max(suf[i][k],dp[i][j][k]);
                            ans=max(ans,dp[i][j][k]);
                        }
                        if(dp[i][j][k]<suf[i-1][qq]+sum[i][k]-sum[i][j-1]){
                            dp[i][j][k]=suf[i-1][qq]+sum[i][k]-sum[i][j-1];
                            pre[i][j]=max(pre[i][j],dp[i][j][k]);
                            suf[i][k]=max(suf[i][k],dp[i][j][k]);
                              ans=max(ans,dp[i][j][k]);
                        }
                    }
                    
                }
            }
        }

解释一下，pre[i][j]表示第i行，以j为右端点能联通的最大值
suf[i][j]表示第i行以j为左端点能联通的最大值.sum[i][j]表示第i行的前缀和，之前已经先处理了一下第一行，所以这段代码从第二行开始dp
我们分析一下这段代码，发现这是一个n^4的dp，对于300的数据是过不了的，考虑一下优化。
榘蒻想了很久也不会做，于是求助大佬，愤怒学习了一波代码之后，得出了以下结论。
我们只要处理出上一行对于每一个点，他能与上面联通的最大价值就ok，具体看看代码，写在注释里面了

#include <iostream>
#include<algorithm>
#include "cstring"
using namespace std;
#define ll long long
#define maxn 305
#define inf 0x3f3f3f3f
#define mod 998244353
int dp[maxn][maxn][2];
int suf[maxn];
int sum[maxn],a[maxn][maxn];
int main(){
    int t;
    freopen("livada2.in","r",stdin);
    freopen("livada2.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        int n,m;
        int ans=-inf;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&a[i][j]);
                //sum[j]=sum[j-1]+a[i][j];
            }
        }
        sum[0]=0;
        for(int i=1;i<=m;i++)sum[i]=sum[i-1]+a[1][i];
        int cur=0;
        // 先搞第一行
        for(int i=1;i<=m;i++){
            for(int j=i;j<=m;j++){
                dp[i][j][cur]=sum[j]-sum[i-1];
                ans=max(ans,dp[i][j][cur]);
            }
        }
        cur^=1;
        for(int i=2;i<=n;i++){
            //先把当前一行的东西清空，是上两行的东西，没有用
            sum[0]=0;
            for(int j=1;j<=m;j++){
                sum[j]=sum[j-1]+a[i][j];
                suf[j]=-inf;
                for(int k=1;k<=m;k++){
                    dp[j][k][cur]=-inf;
                }
            }
            //这一段是优化的关键
            for(int j=1;j<=m;j++){
                int x=-inf;
                for(int k=m;k>=j;k--){    //这边从后往前搞
                    x=max(x,dp[j][k][cur^1]);  //这句话的意思是找到上一行区间为[j,k:m>j]的联通块的最大价值，从后往前搞的意义在于[j][k-2]这个区间包含于[j][k-1]这个区间
                    suf[k]=max(x,suf[k]);  //suf[k]表示上一行能包含k这个点的区间往上的最大联通块的权值
                }
            }
            for(int j=1;j<=m;j++){
                int x=0;
                for(int k=j;k<=m;k++){
                    x=max(x,suf[k]); //在区间j-k中，x是上一行[j][k]中包含某一段的联通块最大值
                    dp[j][k][cur]=x+sum[k]-sum[j-1];// 加上这一段的区间和，ans求个max
                    ans=max(ans,dp[j][k][cur]);
                }
            }
            cur^=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}
 /*
  input
  1
 3 4
 5 -3 0 0
 -2 3 3 4
 -7 -6 4 -5
  output
  17
*/

这题感觉好难- 。- 还是要多复习复习。