Lvat_s Blog

m<=2。。。

所以直接DP

m=1时

f[i][1][k]表示这一列前i个数选了k个子矩阵(中间的1没有用处)

那么转移就很像最大子段和:f[i][1][k]=max(f[i-1][1][k],f[j][1][k-1]+sum[i]-sum[j]);

前面表示不选择，后面表示选择j-i这一段所能带来的当前情况下的最大得分

m=2时复杂一些

f[i][j][k]表示第一列前i个数第二列前j个数选了k个子矩阵

那么转移分4种情况

1:f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);表示继承上一个状态的结果，不选择i或者j

2:f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);表示选择ix-i这一段所能带来的当前情况下的最大得分

3:f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);表示选择jx-j这一段所能带来的当前情况下的最大得分

4:if(i==j)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);表示同时选择两排所能带来的最大得分

最后输出f[n][n][k]就可以了，表示第一列和第二列都选完了，一共选择了k个子矩阵

难得写一次详细的题解……主要是因为我在狂补DP,DP渣到连前几年的普及组题目都写不出来……

去年NOIP D2T2居然不会写

这都坚定了我要补DP的决心……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int sum[105][5],f[105][105][15],a[105][5],n,m,K;

int main(){
freopen("1084.in","r",stdin);
freopen("1084.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		scanf("%d",&a[i][j]);
		sum[i][j]=sum[i-1][j]+a[i][j];
	}
}
memset(f,-127,sizeof(f));
if(m==1){
	for(int i=0;i<=n;i++)f[i][1][0]=0;
	for(int i=1;i<=n;i++){
		for(int k=1;k<=K;k++){
			f[i][1][k]=f[i-1][1][k];
			for(int j=0;j<i;j++){
				f[i][1][k]=max(f[i][1][k],f[j][1][k-1]+sum[i][1]-sum[j][1]);
			}
		}
	}
	printf("%d\n",f[n][1][K]);
}
else if(m==2){
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)f[i][j][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=K;k++){
				f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
				for(int ix=0;ix<i;ix++)f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);
				for(int jx=0;jx<j;jx++)f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);
				if(i==j)for(int x=0;x<i;x++)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);
			}
		}
	}
	printf("%d\n",f[n][n][K]);
}
return 0;
}