[文章目录]
Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。1≤n≤100,1≤m≤2,1≤k≤10
发现m<=2，分情况dp即可。注意转移的时候，当前行和上一行满足作为同一个子矩阵时也可以当做新开了个矩阵。m=2的时候，存在着5种状态（两列为同一个矩阵）。dp[i][j][k]第i行，已有j个矩阵，当前边界状态为k的最大收益
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k;
int dp1[110][12][2],mp1[110],mp2[110];
int dp[110][12][5];
int main()
{
scanf("%d%d%d",&n,&m,&k);
if(m==1)
{
for(int i=1;i<=n;++i) scanf("%d",mp1+i);
memset(dp1,0xef,sizeof dp1);
for(int i=0;i<=n;++i) dp1[i][0][0]=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=k;++j)
{
dp1[i][j][0]=max(dp1[i-1][j][0],dp1[i-1][j][1]);
dp1[i][j][1]=max(max(dp1[i-1][j][1],dp1[i-1][j-1][1]),dp1[i-1][j-1][0])+mp1[i];
}
}
printf("%d",max(dp1[n][k][0],dp1[n][k][1]));
}
else
{
for(int i=1;i<=n;++i) scanf("%d%d",mp1+i,mp2+i);
memset(dp,0xef,sizeof dp);
for(int i=0;i<=n;++i) dp[i][0][0]=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=k;++j)
{
dp[i][j][0]=max(dp[i-1][j][0],max(dp[i-1][j][1],max(dp[i-1][j][2],max(dp[i-1][j][3],dp[i-1][j][4]))));
dp[i][j][1]=max(dp[i-1][j-1][0],max(dp[i-1][j-1][1],max(dp[i-1][j][1],max(dp[i-1][j-1][2],
max(dp[i-1][j-1][3],max(dp[i-1][j][3],dp[i-1][j-1][4]))))))+mp2[i];
dp[i][j][2]=max(dp[i-1][j-1][0],max(dp[i-1][j-1][1],max(dp[i-1][j][2],max(dp[i-1][j-1][2],
max(dp[i-1][j-1][3],max(dp[i-1][j][3],dp[i-1][j-1][4]))))))+mp1[i];
if(j>1) dp[i][j][3]=max(dp[i-1][j-2][0],max(dp[i-1][j-2][1],max(dp[i-1][j-2][2],max(dp[i-1][j-2][3],dp[i-1][j-2][4]))))+mp1[i]+mp2[i];
dp[i][j][3]=max(dp[i][j][3],max(dp[i-1][j-1][1],max(dp[i-1][j-1][2],max(dp[i-1][j-1][3],dp[i-1][j][3])))+mp1[i]+mp2[i]);
dp[i][j][4]=max(dp[i-1][j-1][0],max(dp[i-1][j-1][1],max(dp[i-1][j-1][2],max(dp[i-1][j-1][3],max(dp[i-1][j-1][4],dp[i-1][j][4])))))+mp1[i]+mp2[i];
}
}
printf("%d",max(dp[n][k][0],max(dp[n][k][1],max(dp[n][k][2],max(dp[n][k][3],dp[n][k][4])))));
}
return 0;
}