题目描述

Description

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

Input

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

Output

只有一行为k个子矩阵分值之和最大为多少。

Sample Input

3 2 2
1 -3
2 3
-2 3

Sample Output

9

题目分析

既然m这么小 那么分开考虑
m=1 时 定义表示到i行 选出了j个子矩阵 并且第i行必须选的方案数 然会随便推一下就好了
m=2 时 定义表示到i行 选出了j个子矩阵
并且最后一行是k状态的方案数
其中k只有5种 分别是 不选 只选左边一块 只选右面一块 两块合一块考虑 两块单独考虑
然后推一下就好了
代码不忍直视

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,k;
int mp[200][5],a[201],sum[210][210],f[210][210];
int dp[210][210][30];
int main()
{   
    scanf("%d%d%d",&n,&m,&k);
    if(m==1)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            sum[i][i]=a[i];
            int tmp=a[i];
            for(int j=i-1;j>=1;j--)
                tmp+=a[j],sum[i][j]=max(sum[i][j+1],tmp);
        }
        int ans=0;
        f[1][1]=a[1],f[1][0]=0;
        for(int i=2;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                f[i][j]=f[i-1][j]+a[i];
                for(int l=i-1;l>=1;l--)
                    f[i][j]=max(f[l][j-1]+sum[i][l+1],f[i][j]);
            }
            ans=max(ans,f[i][k]);
        }
        printf("%d",ans);
    }
    else
    {
        int ans=-0x7f7f7f7f;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=2;j++) scanf("%d",&mp[i][j]);
        memset(dp,0xcf,sizeof dp);
        for(int i=1;i<=n;i++) dp[i][0][5]=0;
        dp[1][1][1]=mp[1][1];
        dp[1][1][2]=mp[1][2];
        dp[1][1][3]=dp[1][2][4]=mp[1][1]+mp[1][2];
        for(int i=2;i<=n;i++)
            for(int j=1;j<=k;j++)
            {
                int tmp=max(dp[i-1][j-1][1],max(dp[i-1][j-1][2],max(dp[i-1][j-1][3],max(dp[i-1][j-1][4],dp[i-1][j-1][5]))));
                dp[i][j][5]= max(dp[i-1][j][1],max(dp[i-1][j][2],max(dp[i-1][j][3],max(dp[i-1][j][4],dp[i-1][j][5]))));
                dp[i][j][1]= max(tmp,max(dp[i-1][j][1],dp[i-1][j][4]));
                dp[i][j][2]= max(tmp,max(dp[i-1][j][2],dp[i-1][j][4]));
                dp[i][j][3]= max(tmp,dp[i-1][j][3]);
                dp[i][j][4]= max(dp[i-1][j][4],max(dp[i-1][j-1][1],max(dp[i-1][j-1][2],dp[i-1][j-1][4])));      
                if(j>1) 
                dp[i][j][4]= max(dp[i][j][4],max(dp[i-1][j-2][1],max(dp[i-1][j-2][2],max(dp[i-1][j-2][3],max(dp[i-1][j-2][4],dp[i-1][j-2][5])))));
                dp[i][j][1]+=mp[i][1];
                dp[i][j][2]+=mp[i][2];
                dp[i][j][3]+=mp[i][1]+mp[i][2];
                dp[i][j][4]+=mp[i][1]+mp[i][2];
            }
        printf("%d",max(dp[n][k][1],max(dp[n][k][2],max(dp[n][k][3],max(dp[n][k][4],dp[n][k][5])))));
    }
    return 0;
}