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

果然DP还是需要多练……

f[i][j][p]保存当第i行为p状态时选了j个正方形的最大值

p=1这一行只选左边

p=2这一行只选右边

p=3这一行选两个(但两个为独立的)

p=4这一行选两个(两个并在一起)

 

1 #include
     
       2 #include
      
         3 using namespace std; 4  5 int max5(int a,int b,int c,int d,int e) 6 { 7     return max(max(a,b),max(max(c,d),e));     8 }  9 int max3(int a,int b,int c)10 {11     return max(max(a,b),c);12 }13 int f[101][101][10],n,m,k,x,y,z;14 int main()15 {16     cin>>n>>m>>k;17     if (m==1)18     {19         for (int i=1;i<=n;++i)20         {21             cin>>x;22             for (int j=1;j<=k;++j)23             {24                 f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]);25                 f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+x;26             }27         }28         cout<
       
        >x>>y;39             z=x+y;40             for (int j=1;j<=k;++j)41             {42                 f[i][j][0]=max5(f[i-1][j][0],f[i-1][j][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j][4]);43                 f[i][j][1]=max5(f[i-1][j-1][0]+x,f[i-1][j][1]+x,f[i-1][j-1][2]+x,f[i-1][j][3]+x,f[i-1][j-1][4]+x);44                 f[i][j][2]=max5(f[i-1][j-1][0]+y,f[i-1][j-1][1]+y,f[i-1][j][2]+y,f[i-1][j][3]+y,f[i-1][j-1][4]+y);45                 f[i][j][3]=max3(f[i-1][j-1][1]+z,f[i-1][j-1][2]+z,f[i-1][j][3]+z);46                 if (j>=2)f[i][j][3]=max3(f[i][j][3],f[i-1][j-2][0]+z,f[i-1][j-2][4]+z);47                 f[i][j][4]=max5(f[i-1][j-1][0]+z,f[i-1][j-1][1]+z,f[i-1][j-1][2]+z,f[i-1][j-1][3]+z,f[i-1][j][4]+z);48                 49             }50         }51         cout<