给一个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 */这题感觉好难- 。- 还是要多复习复习。
