Description

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

不能相互重叠。

Input

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

分值的绝对值不超过32767)。

Output

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

题解：

　　看了半天，突然发现，m小于等于2啊。

　　然后就乱dp一波，除了转移写起来很麻之外，就没什么了。

　　令f[i][j][k]表示当前第i行，以选中j个矩阵，当前行的取法为k的得分数，（取法只有5种啦）。

代码：

#include
      
       using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 105#define inf 0x7fint n,m,k,a[MN][3],ans;int f[MN][15][6];void rw(int &x,int y){
    if(y>x)x=y;}int main(){    n=read(),m=read(),k=read();    register int i,j;    for(i=1;i<=n;i++)for(j=1;j<=m;j++) a[i][j]=read();    if(m==1){        for(i=1;i<=n;i++) for(j=1;j<=k;j++){            rw(f[i][j][0],f[i-1][j][0]);            rw(f[i][j][0],f[i-1][j][1]);            rw(f[i][j][1],f[i-1][j][1]+a[i][1]);            rw(f[i][j][1],f[i-1][j-1][0]+a[i][1]);        }        printf("%d\n",max(f[n][k][1],f[n][k][0]));    }    else{        memset(f,-inf,sizeof f);        for(i=0;i<=n;i++)for(j=0;j<=k;j++) f[i][j][1]=0;        for(i=1;i<=n;i++)for(j=1;j<=k;j++){            for(int h=1;h<=5;h++) rw(f[i][j][1],f[i-1][j][h]);                        f[i][j][2]=max(f[i-1][j][2],f[i-1][j][5])+a[i][1];            f[i][j][3]=max(f[i-1][j][3],f[i-1][j][5])+a[i][2];            rw(f[i][j][2],f[i-1][j-1][4]+a[i][1]);            rw(f[i][j][3],f[i-1][j-1][4]+a[i][2]);            rw(f[i][j][2],max(f[i-1][j-1][1],f[i-1][j-1][3])+a[i][1]);            rw(f[i][j][3],max(f[i-1][j-1][1],f[i-1][j-1][2])+a[i][2]);                        f[i][j][4]=max(f[i-1][j-1][1],f[i-1][j][4])+a[i][1]+a[i][2];            rw(f[i][j][4],max(f[i-1][j-1][2],f[i-1][j-1][3])+a[i][1]+a[i][2]);            rw(f[i][j][4],f[i-1][j-1][5]+a[i][1]+a[i][2]);                        f[i][j][5]=f[i-1][j][5]+a[i][1]+a[i][2];            rw(f[i][j][5],max(f[i-1][j-1][2],f[i-1][j-1][3])+a[i][1]+a[i][2]);            if(j>=2) rw(f[i][j][5],max(f[i-1][j-2][1],f[i-1][j-2][4])+a[i][1]+a[i][2]);        }        ans=-1e12;        for(i=1;i<=5;i++) rw(ans,f[n][k][i]);        printf("%d\n",ans);    }    return 0;}
      

---

来自PaperCloud的博客，未经允许，请勿转载，TKS！