[bzoj1084]最大子矩阵

用f[i][j][k]表示第一行前i个数，第二行前j个数选k个子矩形的答案，考虑转移：
1.在第一行/第二行选择一个矩形
2.当i=j时，可以选择一个两行的矩形
注意要特判m=1的情况

#include<bits/stdc++.h>
using namespace std;
int n,m,t,a[105][3],f[105][15],dp[105][105][15];
int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            a[i][j]+=a[i-1][j];
        }
    if (m==1){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=t;j++){
                f[i][j]=f[i-1][j];
                for(int k=0;k<i;k++)f[i][j]=max(f[i][j],f[k][j-1]+a[i][1]-a[k][1]);
            }
        printf("%d",f[n][t]);
        return 0; 
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=t;k++){
                dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]);
                for(int l=0;l<i;l++)dp[i][j][k]=max(dp[i][j][k],dp[l][j][k-1]+a[i][1]-a[l][1]);
                for(int l=0;l<j;l++)dp[i][j][k]=max(dp[i][j][k],dp[i][l][k-1]+a[j][2]-a[l][2]);
                if (i==j)
                    for(int l=0;l<i;l++)
                        dp[i][j][k]=max(dp[i][j][k],dp[l][l][k-1]+a[i][1]-a[l][1]+a[i][2]-a[l][2]);
            }
    printf("%d",dp[n][n][t]);
}