lp2331 SCOI2001 最大子段和

看起来是一道很简单的题，但是细节巨多，消耗了我大量的提交次数。如果是比赛我怕不是凉了。

很显然是一道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;
}