P2331 [SCOI2005]最大子矩阵

传送门

康康m的范围

m只能取1或者2

先看m=1 是一条链

 那么对于第i个点有三种情况

1 和上面连在一起成一个矩阵

2 和下面连在一起成一个矩阵

3 成为断点

同样的 对于m=2我们也这样分析

但是要注意应该以一行为一个基准

那么就有5种情况

0 不取这一行

1 取左边的点

2 取右边的点

3 两个点都取 并且属于一个矩阵

4 两个点都取 但是属于两个矩阵

按这个思路推转移方程

具体看代码

//P2331 [SCOI2005]最大子矩阵
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int f[105][15][5];
int a[105][3];
int main(){
    cin>>n>>m>>k;
    memset(f,-127,sizeof(f));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=k;j++){
            f[i][j][0]=0;
        }
    }
    int  t;
    if(m==1){
        for(int i=1;i<=n;i++){
            scanf("%d",&t);
            for(int j=1;j<=k;j++){
                f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+t;
                f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]);
            }
        }
        printf("%d",max(f[n][k][0],f[n][k][1]));
        return 0;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){//3 divide 4 together
            f[i][j][0]=max(max(f[i-1][j][0],f[i-1][j][1]),max(max(f[i-1][j][2],f[i-1][j][3]),f[i-1][j][4]));
            f[i][j][1]=max(max(f[i-1][j-1][0],f[i-1][j][1]),max(f[i-1][j-1][2],max(f[i-1][j][3],f[i-1][j-1][4])))+a[i][1];
            f[i][j][2]=max(max(f[i-1][j-1][0],f[i-1][j-1][1]),max(max(f[i-1][j][2],f[i-1][j][3]),f[i-1][j-1][4]))+a[i][2];
            if(j>=2)
                f[i][j][3]=max(max(f[i-1][j-2][0],f[i-1][j-1][1]),max(max(f[i-1][j-1][2],f[i-1][j][3]),f[i-1][j-2][4]))+a[i][1]+a[i][2];
            else
                f[i][j][3]=max(max(f[i-1][j][3],f[i-1][j-1][1]),f[i-1][j-1][2])+a[i][1]+a[i][2];

            f[i][j][4]=max(max(f[i-1][j-1][0],f[i-1][j-1][1]),max(max(f[i-1][j-1][2],f[i-1][j-1][3]),f[i-1][j][4]))+a[i][1]+a[i][2];
        }
    }
    int ans=0;
    for(int i=0;i<=4;i++){
        ans=max(ans,f[n][k][i]);
    }
    cout<<ans;
    return 0;
}