随手翻到了之前做的一道水题，随便写篇题解水一水吧
最大子矩阵，一开始不会，一度以为是神题（划掉）
然后发现m<=2，woc，这不是水题吗？
m==1时
直接求序列分成k段的最大和
m==2时
f[i][j][k]表示上一行还有i个数，下一行还有j个数时取k个子矩阵的最大和
下面是代码（能AC我吃羊羽）
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; int n,m,k,i,j,ans; int jiyi[103][103][23]; int sum[3][102]; int tu[103][4]; int dp(int aa,int bb,int kk){ int& fanhui=jiyi[aa][bb][kk]; if(fanhui!=-1){ return fanhui; }else{ if(kk==0){ fanhui=0; }else{ if(aa>n&&bb>n&&kk>0){ fanhui=-9999999999; return fanhui; } if(aa<=n){ for(int xun=aa;xun<=n;xun++){ fanhui=max(fanhui,dp(xun+1,bb,kk-1)+sum[1][xun]-sum[1][aa-1]); fanhui=max(fanhui,dp(aa+1,bb,kk)); } } if(bb<=n){ for(int xun=bb;xun<=n;xun++){ fanhui=max(fanhui,dp(aa,xun+1,kk-1)+sum[2][xun]-sum[2][bb-1]); fanhui=max(fanhui,dp(aa,bb+1,kk)); } } if(bb<=n&&aa<=n){ for(int xun=max(aa,bb);xun<=n;xun++){ fanhui=max(fanhui,dp(xun+1,xun+1,kk-1)+sum[2][xun]-sum[2][max(aa,bb)-1]+sum[1][xun]-sum[1][max(aa,bb)-1]); } } } } return fanhui; } int main(){ cin>>n>>m>>k; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ cin>>tu[i][j]; sum[j][i]=sum[j][i-1]+tu[i][j]; } } for(i=0;i<=n+2;i++){ for(j=0;j<=n+2;j++){ for(int t=0;t<=k+2;t++){ jiyi[i][j][t]=-1; } } } if(m==1){ ans=dp(1,n+1,k); }else{ ans=dp(1,1,k); } cout<<ans; return 0; }