closefrom

注意到m=1或者2，

当m=1时，是普通的最大连续字段和，只不过是k个：

设dp[i][j]表示前i个数中取出j个矩形的最大和

转移：

选：dp[i][j]=max{dp[l][j-1]+s[i]-s[l-1]}

不选：dp[i][j]=max(dp[i][j],dp[i-1][j])

复杂度O(n^2*K)

当m=2时，设f[i][j][k]表示第一列选到第i个数，第二列选到第j个数时，总共k个子矩形的答案

转移有4种情况

当这一位什么都不做的时候：f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k])

当仅选取第一列的某段区间时：f[i][j][k]=max(f[l][j][k-1]+sum[i][1]-sum[l-1][1]) 1<=l<i

当仅选取第二列的某段区间时：f[i][j][k]=max(f[i][l][k-1]+sum[j][2]-sum[l-1][2]) 1<=l<j

当i==j时，可以选取两列一起的f[i][j][k]=max(f[l][l][k]+sum[i][1]+sum[i][2]-sum[l-1][1]-sum[l-1][2])

最后所有情况取max

复杂度O(n^3*K)

#include <cstdio>
using namespace std;
int n,m,k,x,y;
int dp[105][105][15];//dp[i][j][k] 表示 当前第一列选到第i个数，第二列选到第j个数，已经选出了k个子矩阵，的最大值
int s1[105],s2[105];//s1和s2数组分别表示第一列和第二列的前缀和数组
int max(int a,int b){return a>b?a:b;}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    if(m==1){
        for(int i=1;i<=n;i++)scanf("%d",&x),s1[i]=s1[i-1]+x;
        for(int i=1;i<=k;i++)
            for(int j=1;j<=n;j++){
                dp[j][0][i]=dp[j-1][0][i];
                for(int skr=0;skr<j;skr++)dp[j][0][i]=max(dp[j][0][i],dp[skr][0][i-1]+s1[j]-s1[skr]);
            }
        printf("%d",dp[n][0][k]);
    }else{
        for(int i=1;i<=n;i++)scanf("%d%d",&x,&y),s1[i]=s1[i-1]+x,s2[i]=s2[i-1]+y;
        
        for(int i=1;i<=k;i++)
            for(int j=1;j<=n;j++)
                for(int sk=1;sk<=n;sk++){
                    dp[j][sk][i]=max(dp[j-1][sk][i],dp[j][sk-1][i]);
                    for(int st=0;st<j;st++)dp[j][sk][i]=max(dp[j][sk][i],dp[st][sk][i-1]+s1[j]-s1[st]);
                    for(int su=0;su<sk;su++)dp[j][sk][i]=max(dp[j][sk][i],dp[j][su][i-1]+s2[sk]-s2[su]);
                    if(j==sk)for(int sr=0;sr<j;sr++)dp[j][sk][i]=max(dp[j][sk][i],dp[sr][sr][i-1]+s1[j]+s2[sk]-s1[sr]-s2[sr]);
                }
    /*
    上面三个循环，
    第一个循环表示当前n*2矩阵中选k个矩阵，从1-k推，
    从dp数组的定义来看，第一个转移是，第一列的第j个数不选或者是第sk个数不选的最大值
    一次只操作一列！
    三重循环中的第一重循环 表示，操作第一列数，当前选到了第j个数，则可能第j到前面第st个数之间这个区域可以形成一个 构成答案中的一个矩阵
    第二重循环亦是如此
    最后如果j==sk,也就是第一列和第二列同时选取到同一行的数时，有可能第一列和第二列的第sr行到 第 j（sk）行 构成一个答案中的一个矩阵
    */
    printf("%d",dp[n][n][k]);
    }
    return 0;
}