首先题目是要选几个连续的矩阵，有关连续类的问题是可以最优值直接在相邻两行转移的
而且题目中m<=2是非常方便的条件，分类讨论就可以了
注： 0 0也要转移
码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define N 205 int n,m,k,a[N][3],f[N][15][15],i,j,l,ans=-1000000009; int main() { scanf("%d%d%d",&n,&m,&k); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&a[i][j]); } for(i=0;i<=200;i++) for(j=0;j<=10;j++) for(l=0;l<=10;l++) f[i][j][l]=-1000000009; f[0][0][0]=0; if(m==1) { for(i=1;i<=n;i++) { f[i][0][0]=f[i-1][0][0]; for(j=1;j<=k;j++) { f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+a[i][1]); //衔接 f[i][j][1]=max(f[i][j][1],f[i-1][j-1][1]);//徒增 f[i][j][1]=max(f[i][j][1],f[i-1][j-1][0]+a[i][1]);//跳选 f[i][j][0]=max(f[i][j][0],f[i-1][j][0]);//不选 f[i][j][0]=max(f[i][j][0],f[i-1][j][1]);//不选 } } }else { for(i=1;i<=n;i++) { f[i][0][0]=f[i-1][0][0]; for(j=1;j<=k;j++) { //1:上1下0 2:上0 下1 3：上1 下1 且一个块 4:上1 下1且不同一块 0:上0下0 f[i][j][1]=max(f[i][j][1],f[i-1][j][1]+a[i][1]); f[i][j][1]=max(f[i][j][1],f[i-1][j-1][2]+a[i][1]); f[i][j][1]=max(f[i][j][1],f[i-1][j-1][3]+a[i][1]); f[i][j][1]=max(f[i][j][1],f[i-1][j][4]+a[i][1]); f[i][j][1]=max(f[i][j][1],f[i-1][j-1][0]+a[i][1]); f[i][j][2]=max(f[i][j][2],f[i-1][j-1][1]+a[i][2]); f[i][j][2]=max(f[i][j][2],f[i-1][j][2]+a[i][2]); f[i][j][2]=max(f[i][j][2],f[i-1][j-1][3]+a[i][2]); f[i][j][2]=max(f[i][j][2],f[i-1][j][4]+a[i][2]); f[i][j][2]=max(f[i][j][2],f[i-1][j-1][0]+a[i][2]); f[i][j][3]=max(f[i][j][3],f[i-1][j-1][1]+a[i][2]+a[i][1]); f[i][j][3]=max(f[i][j][3],f[i-1][j-1][2]+a[i][2]+a[i][1]); f[i][j][3]=max(f[i][j][3],f[i-1][j][3]+a[i][2]+a[i][1]); f[i][j][3]=max(f[i][j][3],f[i-1][j-1][4]+a[i][2]+a[i][1]); f[i][j][3]=max(f[i][j][3],f[i-1][j-1][0]+a[i][2]+a[i][1]); f[i][j][4]=max(f[i][j][4],f[i-1][j-1][1]+a[i][2]+a[i][1]); f[i][j][4]=max(f[i][j][4],f[i-1][j-1][2]+a[i][2]+a[i][1]); f[i][j][4]=max(f[i][j][4],f[i-1][j][4]+a[i][2]+a[i][1]); f[i][j][0]=max(f[i][j][0],f[i-1][j][1]); f[i][j][0]=max(f[i][j][0],f[i-1][j][2]); f[i][j][0]=max(f[i][j][0],f[i-1][j][3]); f[i][j][0]=max(f[i][j][0],f[i-1][j][4]); f[i][j][0]=max(f[i][j][0],f[i-1][j][0]); } } } for(i=0;i<=10;i++) ans=max(ans,f[n][k][i]); printf("%d",ans); }