[BZOJ1084/Luogu2331][SCOI2005]最大子矩阵(动态规划)

发布于 2018-02-02  60 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1084/Luogu2331][SCOI2005]最大子矩阵(动态规划)

Description

这里有一个n*m的矩阵,请你选出其中k个子矩阵,使得这个k个子矩阵分值之和最大。注意:选出的k个子矩阵
不能相互重叠。

Http

BZOJ
Luogu

Tag

动态规划

解决思路

看到m的范围就知道是动态规划了。分\(m=1\)和\(m=2\)两种情况讨论。
先是\(m=1\)的。设\(F[i][j]\)表示前\(j\)个数中选出\(i\)个子矩阵的最大和,那么首先它可以从\(F[i][j-1]\)转移过来,这个的意思是取这一层这一次的最大,然后可以枚举一个\(k\)从\(F[i-1][k]\)转移过来。
对于\(m=2\)的则类似设\(F[i][j][k]\)表示第一列选到\(j\),第二列选到\(k\),选出\(i\)个子矩阵的最大和,那么类比\(m=1\)的转移,它首先可以从\(F[i][j-1][k]\)和\(F[i][j][k-1]\)中大的那个转移过来,再分别枚举\(pos\)小于\(j\)和小于\(k\)分别从前面转移过来,这个是表示选择其中的一列的子矩阵。最后若\(j==k\),则还可以从同时选择两行转移过来。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=101;
const int maxM=3;
const int maxK=11;
const int inf=2147483647;

int n,m,K;
int Mat[maxN][maxM],Sum[maxN][maxM];
int F1[maxK][maxN];
int F2[maxK][maxN][maxN];

void Do1();
void Do2();

int main()
{
    scanf("%d%d%d",&n,&m,&K);
    if (m==1) Do1();
    else Do2();
    return 0;
}

void Do1()
{
    for (int i=1;i<=n;i++) scanf("%d",&Mat[i][1]),Sum[i][1]=Sum[i-1][1]+Mat[i][1];
    F1[0][0]=0;
    for (int i=1;i<=K;i++)
        for (int j=1;j<=n;j++)
        {
            F1[i][j]=F1[i][j-1];//这一步保证从前面取得最优值
            for (int k=0;k<j;k++)
                F1[i][j]=max(F1[i][j],F1[i-1][k]+Sum[j][1]-Sum[k][1]);
        }
    printf("%d\n",F1[K][n]);
    return;
}

void Do2()
{
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&Mat[i][1],&Mat[i][2]);
        Sum[i][1]=Sum[i-1][1]+Mat[i][1];
        Sum[i][2]=Sum[i-1][2]+Mat[i][2];
    }
    F2[0][0][0]=0;
    for (int i=1;i<=K;i++)
        for (int j=1;j<=n;j++)
            for (int k=1;k<=n;k++)
            {
                F2[i][j][k]=max(F2[i][j-1][k],F2[i][j][k-1]);
                for (int pos=0;pos<j;pos++) F2[i][j][k]=max(F2[i][j][k],F2[i-1][pos][k]+Sum[j][1]-Sum[pos][1]);
                for (int pos=0;pos<k;pos++) F2[i][j][k]=max(F2[i][j][k],F2[i-1][j][pos]+Sum[k][2]-Sum[pos][2]);
                if (j==k)
                    for (int pos=0;pos<j;pos++) F2[i][j][k]=max(F2[i][j][k],F2[i-1][pos][pos]+Sum[j][1]-Sum[pos][1]+Sum[k][2]-Sum[pos][2]);
            }
    printf("%d\n",F2[K][n][n]);
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1084/Luogu2331][SCOI2005]最大子矩阵(动态规划)


HNCJ OIer