[SCOI2005] 最大子矩阵

题意

矩形的每一个格子有权值

一个宽 1 或 2 的矩形选出 k 个子矩形,问最大权值和

分析

既然宽度只有 2, 状压一下每行状态 DP 即可

定义 表示前 行选 个子矩形的最大权值. 其中 k:

  • k=0 表示第 行没有选
  • k=1 表示第 行选左边的矩形
  • k=2 表示第 行选右边的矩形
  • k=3 表示第 行选宽度为 2 的矩形
  • k=4 表示第 行选两个并排宽度为 1 的矩形

转移即可

m=1 同理, 要更简单一些

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=105,K=12;
int n,m,k;
int a[N][2];

int solve1(){int f[N][K][2];
    memset(f,-0x3f,sizeof(f));
    f[0][0][0]=0;
    for(int i=1;i<=n+1;i++){for(int j=0;j<=k;j++){//f[i][j][0]
            f[i][j][0]=max(f[i][j][0],f[i-1][j][0]);
            f[i][j][0]=max(f[i][j][0],f[i-1][j][1]);
            //f[i][j][1]
            f[i][j][1]=max(f[i][j][1],f[i][j-1][0]);
            f[i][j][1]=max(f[i][j][1],f[i-1][j][1]);
            f[i][j][1]+=a[i][0];
        }
    }
    return f[n+1][k][0];
}
int solve2(){int f[N][K][5];
    memset(f,-0x3f,sizeof(f));
    f[0][0][0]=0;
    for(int i=1;i<=n+1;i++){for(int j=0;j<=k;j++){//f[i][j][0]
            for(int p=0;p<5;p++)f[i][j][0]=max(f[i][j][0],f[i-1][j][p]);
            //f[i][j][1]
            f[i][j][1]=max(f[i][j][1],f[i-1][j][1]);// 和上一行相连
            f[i][j][1]=max(f[i][j][1],f[i-1][j][4]);
            if(j>0)f[i][j][1]=max(f[i][j][1],f[i][j-1][0]);// 独自成一个矩形
            f[i][j][1]+=a[i][0];
            //f[i][j][2]
            f[i][j][2]=max(f[i][j][2],f[i-1][j][2]);
            f[i][j][2]=max(f[i][j][2],f[i-1][j][4]);
            if(j>0)f[i][j][2]=max(f[i][j][2],f[i][j-1][0]);
            f[i][j][2]+=a[i][1];
            //f[i][j][3],横放 1*2
            f[i][j][3]=max(f[i][j][3],f[i-1][j][3]);
            if(j>0)f[i][j][3]=max(f[i][j][3],f[i][j-1][0]);
            f[i][j][3]+=a[i][0]+a[i][1];
            //f[i][j][4],并排纵向
            f[i][j][4]=max(f[i][j][4],f[i-1][j][4]);
            if(j>1)f[i][j][4]=max(f[i][j][4],f[i][j-2][0]);// 独自成两个
            if(j>0)f[i][j][4]=max(f[i][j][4],f[i-1][j-1][1]);// 左边连通,右边多一个
            if(j>0)f[i][j][4]=max(f[i][j][4],f[i-1][j-1][2]);// 右边连通,左边多一个
            f[i][j][4]+=a[i][0]+a[i][1];
        }
    }
    return f[n+1][k][0];
}

int main(){scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)for(int j=0;j<m;j++)scanf("%d",&a[i][j]);
    printf("%d",m==1?solve1():solve2());
    return 0;
}

 上一篇
博弈论 博弈论
摘要 博奕论,一门高深的学问。 2019.6.15 编入精选文章。 dls 讲博弈论:“你掉线,我随意” 博弈的分类博弈大体分为平等博弈和不平等博弈。平等博弈指双方的决策集等价,不平等博弈则指双方决策集不等价。 常见的平等博弈则则是 I
2018.12.13
下一篇 
[HAOI2007] 理想的正方形 [HAOI2007] 理想的正方形
题意有一个 的整数组成的矩阵,现请你从中找出一个 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 分析好多人用什么倍增的算法,还有用线段树的。。。 我们考虑一下,要求以 $(i
2018.12.08
  目录