【DP专题】——洛谷P2331最大子矩阵

简单的动规题。

传送门：GO

---

看到这题m<=2,先分类讨论一波：

m=1时，dp[i][j]表示到第i个点，选了j个矩阵的最大子矩阵。

状态转移方程：

　　dp[i][j]=dp[t][j-1]+sum[i]-sum[t]

意思是枚举一段区间，将它设为新的矩阵。

m=2时，设dp[i][j][k]表示第i行，状态为j，此时选到k个矩阵时的最大子矩阵。

设计状态：

1.空的

2.只选左边

3.只选右边

4.两边都选，但是左边和右边归为两个子矩阵

5.两边都选，分配到上面

分别讨论状态转移，大致有25个转移方程(好多)

具体看代码就可以了。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=110;
int n,m,k;
int b[N];
int f[N][15][10];
int g[N][15];
int main(){
    n=read();m=read();k=read();
    if(m==1){
        for(int i=1;i<=n;i++){
            b[i]=b[i-1]+read();
        }
        for(int i=1;i<=k;i++){
            for(int j=1;j<=n;j++){
                g[j][i]=g[j-1][i];
                for(int l=1;l<j;l++){
                    g[j][i]=max(g[j][i],g[l][i-1]+b[j]-b[l]);
                }
            }
        }
        printf("%d",g[n][k]);
        return 0;
    }
    else{
        memset(f,-0x3f,sizeof(f));
        for(int i=0;i<=n;i++){
            for(int j=0;j<=k;j++){
                f[i][j][0]=0;
            }
        }
        int l,r;
        for(int i=1;i<=n;i++){
            l=read();r=read();
            for(int j=1;j<=k;j++){
                f[i][j][0]=max(max(max(max(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]);
                f[i][j][1]=max(max(max(max(f[i-1][j-1][0],f[i-1][j][1]),f[i-1][j-1][2]),f[i-1][j][3]),f[i-1][j-1][4])+l;
                f[i][j][2]=max(max(max(max(f[i-1][j-1][0],f[i-1][j-1][1]),f[i-1][j][2]),f[i-1][j][3]),f[i-1][j-1][4])+r;
                f[i][j][3]=max(max(f[i-1][j-1][1],f[i-1][j-1][2]),f[i-1][j][3])+l+r;
                f[i][j][4]=max(max(max(max(f[i-1][j-1][0],f[i-1][j-1][1]),f[i-1][j-1][2]),f[i-1][j-1][3]),f[i-1][j][4])+l+r;
            }
        }
        printf("%d",max(max(max(max(f[n][k][0],f[n][k][1]),f[n][k][2]),f[n][k][3]),f[n][k][4]));
        return 0;
    }
    return 0;
    
}