洛谷 P1854 花店橱窗布置/ACWing 313 花店橱窗 题解

2019-12-26 xiaoh

题意

给定f盆花，v个花盆(1<=f<=v<=100)。第i朵花插在第j个花盆中都有一个美丽值Aij（Aij可能为负数）。现在你要将所有花按照原有的顺序全部插进花盆中，求最大的美学值之和（保证答案在int范围内），并输出对应的方案（ACWing要求字典序最小，洛谷无特殊要求）

题解

先考虑如何求美学值。令f[i][j]为前i盆花摆进前j个盆子的最大美学值，则有以下几种情况：

1、第j个瓶子什么也不放，即f[i][j]=max(f[i][j-1],f[i][j])

2、将花放进第j个盆子。那么遍历前面所有放过第i-1朵花的瓶子并取最大值，转移，即f[i][j]=MAX{f[i-1][k]+a[i][j]}，k∈[i-1,j-1]。

我们令f[0][x]=0,x∈[0,v],其余全为-inf即可计算最大值。接下来考虑如何输出方案。首先，我们可以将DP的过程理解为类似一个走方格的过程，我们只需在DP时记录每个节点是从哪个点转移过来的即可，然后每次从f[n][m]开始倒着搜到起点，然后一路找回来并输出即可。

Code

#include<bits/stdc++.h>
#define inf 999999999
using namespace std;
inline int read()//快读
{
    int ret=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return w*ret;
}
int n,m;
int a[110][110];//原数组
struct node{
    int pos,num;
    int p;
}f[110][110];//DP数组，其中p表示第i朵花插在第几个花瓶里，pos是转移位置
void find(int step,int x)//沿着记录下的转移位置一路找回去，并输出
{
    if(step==0) return;
    find(step-1,f[step][x].pos);
    printf("%d ",x);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) a[i][j]=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) f[i][j].num=-inf;//初始化
    for(int i=1;i<=n;i++)
    for(int j=i;j<=m;j++)
    {
        f[i][j].pos=f[i][j-1].pos;//第j个花瓶什么也不放
        f[i][j].num=f[i][j-1].num;
        f[i][j].p=f[i][j-1].p;
        for(int k=i-1;k<j;k++)//遍历转移点并记录，ACW由于要求字典序最小，因此k要正序遍历
        if(f[i-1][k].num+a[i][j]>f[i][j].num) f[i][j].num=f[i-1][k].num+a[i][j],f[i][j].pos=k,f[i][j].p=j;
    }
    printf("%d\n",f[n][m].num);
    find(n,f[n][m].p);
    printf("\n");
    return 0;
}

洛谷 P1854 花店橱窗布置/ACWing 313 花店橱窗 题解