[bzoj1084][SCOI2005]最大子矩阵_动态规划

最大子矩阵 bzoj-1084 SCOI-2005

题目大意：给定一个n*m的矩阵，请你选出k个互不重叠的子矩阵使得它们的权值和最大。

注释：$1\le n \le 100$，$1\le m\le 2$，$1\le k\le 10$。

想法：不会。。。看了数据范围..卧槽？m<=2?????我们就可以进行一个简单的轮廓线dp。

首先，先分m==1和m==2分类讨论，m==1不说了

m==2

令f[k][i][j]是第一列到了i，第二列到了j，已经选取了k个矩形的最大权值。

转移：有3种转移方式：

1.从左侧转移：f[k][i][j]=max(f[k][i][j] , f[k-1][l][j] + before[1][i] - before[1][l] )。

2.从右侧转移，转移方程同理。

3.选取横跨左右的矩阵，此时必须有i==j：f[k][i][j]=max(f[k][i][j] , f[k-1][l][l] + before[1][i] + before[2][i] - before[1][l] - before[2][l])。

时间复杂度：$O(n^3\cdot k)$。

最后，附上丑陋的代码... ...

#include<iostream>

#include<cstdio>

#define N 110

using namespace std;

int F[12][N],f[12][N][N];

int n,m,K,s[3][N];

int a;

void dispose1()

{

    for(int k=1;k<=K;k++)

        for(int i=1;i<=n;i++)

        {

            F[k][i]=F[k][i-1];

            for(int j=0;j<=i-1;j++) F[k][i]=max(F[k][i],F[k-1][j]+s[1][i]-s[1][j]);

        }

    int ans=0;

    for(int i=0;i<=K;i++) ans=max(ans,F[i][n]);

    printf("%d\n",ans);

}

void dispose2()

{

    for(int i=1;i<=n;i++) s[0][i]=s[1][i]+s[2][i];

    for(int k=1;k<=K;k++) for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

        {

            f[k][i][j]=max(f[k][i-1][j],f[k][i][j-1]);

            for(int l=0;l<i;l++) f[k][i][j]=max(f[k][i][j],f[k-1][l][j]+s[1][i]-s[1][l]);

            for(int l=0;l<j;l++) f[k][i][j]=max(f[k][i][j],f[k-1][i][l]+s[2][j]-s[2][l]);

            if(i==j)  for(int l=0;l<i;l++) f[k][i][j]=max(f[k][i][j],f[k-1][l][l]+s[0][i]-s[0][l]);

        }

    int ans=0;

    for(int i=0;i<=K;i++) ans=max(ans,f[i][n][n]);

    printf("%d\n",ans);

}

int main()

{

    scanf("%d%d%d",&n,&m,&K);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

        {

            scanf("%d",&a);

            s[j][i]=a+s[j][i-1];

        }

    if(m==1) dispose1();

    else dispose2();

    return 0;

}

　　小结：一般情况下，我们能求解的只是简单问题的全部版本和复杂问题的特殊版本，所以要对问题抱有敬畏之心（Orz石总）

巴特西

[bzoj1084][SCOI2005]最大子矩阵_动态规划_伪·轮廓线dp

最新文章

热门文章