[SCOI2005]最大子矩阵

题意：在一个n*m的矩阵中选择k个子矩阵，这k个子矩阵互不相交，求这k个子矩阵分值最大为多少？

思路：dp
dp[k][i][j]为在第一列前i个，第二列前j个，选择k个矩阵的最大值。
分析我们动态所加的一个元素参与结果的情况。既枚举所加元素在第一列前i个，第二列前j个中所有矩阵加上在该矩阵外选（k-1）个子矩阵的值。

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1e9

using namespace std;

ll dp[105][105][105], d[105][5], sum[105][5];

int main()
{
    int n, m, K;
    scanf("%d%d%d",&n,&m,&K);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&d[i][j]);
            sum[i][j]=sum[i-1][j]+d[i][j];
        }
    }
    for(int k=1;k<=K;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[k][i][j]=-inf;
                if(i==j)
                {
                    for(int l=0;l<i;l++)
                    {
                        dp[k][i][j]=max(dp[k][i][j],dp[k-1][l][l]+sum[i][1]-sum[l][1]+sum[j][2]-sum[l][2]);
                    }
                }
                for(int l=0;l<i;l++)
                {
                    dp[k][i][j]=max(dp[k][i][j],dp[k-1][l][j]+sum[i][1]-sum[l][1]);
                }
                for(int l=0;l<j;l++)
                {
                    dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][l]+sum[j][2]-sum[l][2]);
                }
                dp[k][i][j]=max(dp[k][i][j],max(dp[k][i][j-1],dp[k][i-1][j]));
            }
        }
    }
    printf("%lld\n",dp[K][n][n]);
    return 0;
}