BZOJ 1084 (SCOI 2005) 最大子矩阵

1084: [SCOI2005]最大子矩阵

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 3560 Solved: 1779

[Submit][Status][Discuss]

Description

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

不能相互重叠。

Input

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

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

Output

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

Sample Input

3 2 2

1 -3

2 3

-2 3

Sample Output

—————————————————————————————

题解

看着m<=2。。。

好好的前缀和dp就被我写成毒瘤dp+数据分治了。。

当m=1时，dp[i][j][0/1] 表示前i行选了j个矩形当前选或不选，比较好转移。

当m=2时

    设dp[i][j][0/1/2/3/4] 表示前i行选了j个矩形。

    1代表当前行只选左边，2代表只选左边，0代表都不选，3代表都选但分别是两个矩形中，4代表都选且

    在一个矩形中。然后就是一波瞎搞了。。。

代码

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 105;

int f[MAXN][15][5],n,m,k,a[MAXN][4];

int main(){

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

    if(m==1){

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

            scanf("%d",&a[i][1]);

            for(int j=1;j<=k;j++){

                f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+a[i][1];

                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]));

    }

    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;

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

            scanf("%d%d",&a[i][1],&a[i][2]);

            for(int j=1;j<=k;j++){

                f[i][j][0]=max( max(f[i-1][j][0],f[i-1][j][1]), max(f[i-1][j][2],f[i-1][j][3]));

                f[i][j][0]=max(f[i][j][0],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],f[i-1][j][3]))+a[i][1];

                f[i][j][1]=max(f[i][j][1], 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(f[i-1][j][2],f[i-1][j][3]))+a[i][2];

                f[i][j][2]=max(f[i][j][2], f[i-1][j-1][4]+a[i][2]);

                f[i][j][3]=max(f[i-1][j-1][1],max(f[i-1][j-1][2],f[i-1][j][3]))+a[i][1]+a[i][2];

                if(j>=2) f[i][j][3]=max(f[i][j][3],f[i-1][j-2][4]+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(f[i-1][j-1][2],f[i-1][j-1][3]))+a[i][1]+a[i][2];

                f[i][j][4]=max(f[i][j][4],f[i-1][j][4]+a[i][1]+a[i][2]);

            }

        }

        printf("%d",max( max( max(f[n][k][0],f[n][k][1]), max(f[n][k][2],f[n][k][3])),f[n][k][4]));

    }

    return 0;

}

巴特西

BZOJ 1084 (SCOI 2005) 最大子矩阵

—————————————————————————————

题解

代码

最新文章

热门文章