这是一道神奇的DP。。。矩形可以为空哦~。。。方法好像很多。。。QVQ
对于暴力的 n^4 做法。。。大佬们肯定都明白。。。蒟蒻就不在赘述了。。。
直接抄袭一段代码。。。
呆码：
#include<iostream> #include<cstdio> using namespace std; int n,m,k,dp[110][110][11],map[110][3],res[110][3],two[110]; int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&map[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) res[i][j]=res[i-1][j]+map[i][j]; for(int i=1;i<=n;i++) two[i]=two[i-1]+map[i][1]+map[i][2]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { for(int p=k;p>=1;p--) { dp[i][j][p]=max(dp[i][j-1][p],dp[i-1][j][p]); for(int i1=1;i1<=i;i1++) dp[i][j][p]=max(dp[i][j][p],dp[i1-1][j][p-1]+res[i][1]-res[i1-1][1]); for(int i1=1;i1<=j;i1++) dp[i][j][p]=max(dp[i][j][p],dp[i][i1-1][p-1]+res[j][2]-res[i1-1][2]); for(int i1=1;i1<=min(i,j);i1++) dp[i][j][p]=max(dp[i][j][p],dp[i1-1][i1-1][p-1]+two[min(i,j)]-two[i1-1]); } } printf("%d ",dp[n][n][k]); return 0; }
emm。。。事实上博主想出了一种神奇的 nk 解法。。。
因为我们可以发现数据范围中的 m 是小于等于2的。。。那么假如m=1
这个dp方程应该是可以轻松推出来的。。。（博主推了半个小时）
然后我们可以考虑如何拓展到m=2
因为其情况较少，那么对每一行读入的数我们维护如下几个情况就可以了。。。
0：这两个值宝宝都不选。。。QVQ
1：选取左边的，留下右边的。。。
2：选取右边的，留下左边的。。。
3：两个都选取，但是让他们分开成为两个集合。。。
（这里要特别说明一下。。。其实通过简单的意想就可以发现，实际上让他们单独成为两个集合和组成一个
如果不加入别的操作。。。最后的结果都是一样的。。。但当我们需要进行 1,2 操作时。。。
因为对于 f 数组我们要保证较坏的情况不被考虑。。。那么初始值除了 0 其他情况都是 -inf
那么其前一个状态从哪里来呢？自然就是我的 3 操作了。。。QVQ）
4：两个都选，作为一个矩阵。。。
这样我们就可以动用神级垃圾操作：模拟
对一组数据进行手动模拟就好了。。。QVQ。。。dp柿子就推出来了。。。
其实大体思路明白了。。。柿子意会一下。。。手玩一下数据也就出来了。。。
呆码：
#include<iostream> #include<cstdio> #include<cstring> #define inf 999999 using namespace std; int n,m,k,x,y,f[110][11][5]; int main() { scanf("%d%d%d",&n,&m,&k); if(m==1) { for(int i=1;i<=n;i++) { scanf("%d",&x); for(int j=1;j<=k;j++) { f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+x; f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]); } } printf("%d ",max(f[n][k][0],f[n][k][1])); } else { memset(f,-inf,sizeof(f)); for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) f[i][j][0]=0; for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); for(int j=1;j<=k;j++) { f[i][j][0]=max(f[i-1][j][0],max(max(f[i-1][j][1],f[i-1][j][2]),max(f[i-1][j][3],f[i-1][j][4]))); f[i][j][1]=max(max(max(f[i-1][j-1][4],f[i-1][j-1][0]),f[i-1][j][3]),max(f[i-1][j][1],f[i-1][j-1][2]))+x; f[i][j][2]=max(max(max(f[i-1][j-1][4],f[i-1][j-1][0]),f[i-1][j][3]),max(f[i-1][j-1][1],f[i-1][j][2]))+y; f[i][j][3]=max(max(f[i-1][j-1][1],f[i-1][j-1][2]),f[i-1][j][3])+x+y; if(j>=2) f[i][j][3]=max(f[i][j][3],max(f[i-1][j-2][4],f[i-1][j-2][0])+x+y); f[i][j][4]=max(max(max(f[i-1][j-1][0],f[i-1][j-1][3]),max(f[i-1][j-1][1],f[i-1][j-1][2])),f[i-1][j][4])+x+y; } } printf("%d ",max(max(max(f[n][k][0],f[n][k][1]),max(f[n][k][2],f[n][k][3])),f[n][k][4])); } }