[SCOI2005]最大子矩阵（dp）

题意：略

题记：由于m的范围在1 ≤ m ≤ 2。所以很容易就想到dp。
dp[i][j][k]表示的是在第一列的前i个数，第二列的前j个数选k个矩阵的最大值。

那么dp过程中大致有两种情况：
1、不需要重新选一个新矩阵
dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][k]);

2、需要重新选一个新矩阵：
首先矩阵也分为两种（l为矩阵长度）
（1）1乘l的矩阵

dp[i][j][k]=max(dp[i][l][k-1]+sum[j][2]-sum[l][2],dp[i][j][k]);
dp[i][j][k]=max(dp[l][j][k-1]+sum[i][1]-sum[l][1],dp[i][j][k]);

（2）2乘l的矩阵（只有i==j时候才有2乘l的矩阵）
dp[i][j][k]=max(dp[l][l][k-1]+sum[i][1]-sum[l][1]+sum[j][2]-sum[l][2],dp[i][j][k]);

枚举所有l的长度，全部取一个最大值，最后dp[n][n][p]就是答案。

#include<bits/stdc++.h>

using namespace std;
const int N=110;
int a[N][3],sum[N][3];
int dp[N][N][N];
int main(){
    int n,m,p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=p;k++){
                dp[i][j][k]=max(dp[i][j-1][k],dp[i-1][j][k]);
                //不需要重新选一个新矩阵的情况
                for(int l=0;l<j;l++)
                    dp[i][j][k]=max(dp[i][l][k-1]+sum[j][2]-sum[l][2],dp[i][j][k]);
                //枚举右边选一个新矩阵的长度
                for(int l=0;l<i;l++)
                    dp[i][j][k]=max(dp[l][j][k-1]+sum[i][1]-sum[l][1],dp[i][j][k]);
                //枚举左边选一个新矩阵的长度
                if(i==j){
                    //当i==j时可以选一个2*l的新矩阵
                    for(int l=0;l<i;l++)
                        dp[i][j][k]=max(dp[l][l][k-1]+sum[i][1]-sum[l][1]+sum[j][2]-sum[l][2],dp[i][j][k]);
                }
            }
        }
    }
    cout<<dp[n][n][p]<<endl;
    return 0;
}