看起来是一道很简单的题，但是细节巨多，消耗了我大量的提交次数。如果是比赛我怕不是凉了。
很显然是一道DP题。
很容易可以想到的是暴力枚举，然而这样做的复杂度是O(n^2*n^2k)的，很很很很显然可以发现是不可行的。
观察数据范围，我们可以注意到， m<=2，因此很容易可以想到状压DP。
具体来说，当m==2时，用f[i][j][l]表示，当前处于第i行，第i行的状态为j，已经使用了l个子矩阵时，最大的和。
则状态转移方程是：
f[i][0][l]=Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l]));
f[i][1][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l]))+b[i];
f[i][2][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l]))+a[i];
f[i][3][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l]))+a[i]+b[i];并且我们很容易可以得到边界条件，即：
f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][1]=a[1]+b[1];另外需要考虑m==1的情况，事实上这种情况更容易考虑：状态转移方程是：
f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; 初始化f[1][0][0]=0,f[1][1][1]=a[1];
然而交上去全wa
回头考虑这个问题我们可以发现一个很尴尬的事情：当上一行两个取的时候，我们并不知道它到底是「两列分别取」还是「两列一起取」。
因此，对于11的状态，我们应当拆成两个部分：
f[i][3][l]表示上一行的两列是分别取的。于是得到状态转移方程。
f[i][4][l]表示上一行的两列是合在一起取的。
f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];然而这样子还是全WA。
仔细观察一下我们的状态转移方程，我们发现存在一些l-2的状态，那么我们应该分两类讨论：l==1或l>=2.
这样大概就能通过了。
#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
int n,m,k,f[105][5][15],a[105],b[105];
void slv1(){
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
f[1][0][0]=0,f[1][1][1]=a[1];
for(int i=1;i<=n;++i){
f[i][0][0]=f[i][1][0]=0;
for(int l=1;l<=k;++l){
f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i];
}
}
int ans=-0x3f3f3f3f;
printf("%d",Max(f[n][0][k],f[n][1][k]));
return;
}
void slv2(){
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i],&b[i]);
}
f[0][0][0]=0;
f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][2]=a[1]+b[1],f[1][4][1]=a[1]+b[1];
for(int i=1;i<=n;++i){
f[i][0][0]=f[i][1][0]=f[i][2][0]=f[i][3][0]=f[i][4][0]=0;
for(int l=1;l<=k;++l){
f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];
if(l<2){
continue;
}
f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
}
}
/*
for(int i=1;i<=n;++i){
for(int l=0;l<=k;++l){
for(int j=0;j<5;++j){
printf("%d ",f[i][j][l]);
}
puts("");
}
puts("");
}*/
int ans=-0x3f3f3f3f;
for(int i=0;i<5;++i){
ans=Max(ans,f[n][i][k]);
}
printf("%d",ans);
}
void init(){
scanf("%d%d%d",&n,&m,&k);
memset(f,-1,sizeof(f));
if(m==1){
slv1();
}
if(m==2){
slv2();
}
}
int main(){
init();
return 0;
}