[SCOI2005]{zd0}子矩阵

Time Limit:10000MS Memory Limit:165536K
Total Submit:26 Accepted:13
Case Time Limit:1000MS

Description

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和{zd0}。注意：选出的k个子矩阵不能相互重叠。

Input

{dy}行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的{jd1}值不超过32767)。

Output

只有一行为k个子矩阵分值之和{zd0}为多少。

Sample Input

Sample Output

Source
这个明显要DP，一维的太水就不说了。
二维的话，首先预处理出子矩阵的和比较方便。
设Dp(i,a1,a2)为i个矩形，第1列1..a1，第二列1..a2的{zd0}价值，
那么如果{dy}列的a1不放的话，是Dp(i,a1-1,a2)。。。
如果第二列的a2不放的话，是Dp(i,a1,a2-1)。。。
如果放的话枚举上一个状态是O（n）的。
然后只有在a1==a2的时候才枚举宽度为2的矩阵的情况就可以了。。
不过细节很要紧，我WA了半天，这样下去怎么行啊。比赛考到的话肯定悲剧的囧。。
Code：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100+10,maxk=10+1,inf=~0U>>2;
int n,m,k;
//solve 1
inline void Renew(int&x,int c)
{
    x=max(x,c);
}
void Solve1()
{
    int Dp[maxk][maxn]={0};
    int A[maxn]={0};
    for(int i=1;i<=n;i++)cin>>A[i],A[i]+=A[i-1];
    for(int i=1;i<=k;i++)
    {
        for(int j=0;j<=n;j++)
        {
            int&x=Dp[i][j];x=-inf;
            if(j)x=Dp[i][j-1];
            for(int o=0;o<j;o++)
            {
                Renew(x,Dp[i-1][o]+A[j]-A[o]);
            }
        }
    }
    cout<<Dp[k][n]<<endl;
}
//solve 2
void Solve2()
{
    int Dp[maxk][maxn][maxn]={0};
    int A[2][maxn]={0},S[maxn]={0};
    for(int j=1;j<=n;j++)
        for(int i=0;i<2;i++)
            cin>>A[i][j],S[j]+=A[i][j],A[i][j]+=A[i][j-1];
    for(int j=1;j<=n;j++)
        S[j]+=S[j-1];
    for(int i=1;i<=k;i++)
        for(int a1=0;a1<=n;a1++)
            for(int a2=0;a2<=n;a2++)
            {
                int&x=Dp[i][a1][a2];x=-inf;
                if(a1)
                {
                    Renew(x,Dp[i][a1-1][a2]);
                    for(int o=0;o<a1;o++)
                        Renew(x,Dp[i-1][o][a2]+A[0][a1]-A[0][o]);
                }
                if(a2)
                {
                    Renew(x,Dp[i][a1][a2-1]);
                    for(int o=0;o<a2;o++)
                       Renew(x,Dp[i-1][a1][o]+A[1][a2]-A[1][o]);
                }
                if(a1==a2)
                {
                    for(int o=0;o<a1;o++)
                        Renew(x,Dp[i-1][o][o]+S[a1]-S[o]);
                }
            }
    cout<<Dp[k][n][n]<<endl;
}
int main()
{
    //freopen("in","r",stdin);
    cin>>n>>m>>k;
    if(m==1)Solve1();
    else Solve2();
}

9

3 2 2
1 -3
2 3
-2 3