bzoj1084 [SCOI2005]最大子矩阵——背包

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,dp[105][15][3],s1[105],s2[105],f[105][105][15],w[105];
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if(m==1)
    {
        for(int i=1;i<=n;i++)scanf("%d",&w[i]);
        for(int i=1;i<=n;i++)
            for(int j=0;j<=k;j++)
            {
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]);
                if(j)dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0])+w[i];
            }
        printf("%d",max(dp[n][k][0],dp[n][k][1]));
        return 0;
    }
    else
    {
        for(int i=1,a,b;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            s1[i]=s1[i-1]+a;
            s2[i]=s2[i-1]+b;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int l=1;l<=k;l++)
                {
                    f[i][j][l]=max(f[i][j-1][l],f[i-1][j][l]);
                    for(int t=0;t<i;t++)//t从0开始！ 
                        f[i][j][l]=max(f[i][j][l],f[t][j][l-1]+s1[i]-s1[t]);
                    for(int t=0;t<j;t++)
                        f[i][j][l]=max(f[i][j][l],f[i][t][l-1]+s2[j]-s2[t]);
                    if(i==j)
                        for(int t=0;t<i;t++)
                            f[i][j][l]=max(f[i][j][l],f[t][t][l-1]+s1[i]-s1[t]+s2[j]-s2[t]);
                }
        printf("%d",f[n][n][k]);
        return 0;
    }
}