洛谷题单指南-动态规划2-P1854 花店橱窗布置

原题链接：https://www.luogu.com.cn/problem/P1854

题意解读：F束花依次放入V个花瓶，每个花瓶最多一朵，且花的顺序在花瓶中递增，计算最大的美学值，并且输出每朵花具体放置方案。

解题思路：

首先想到的的DFS法，对于每一朵花，枚举所有的摆放方案，累加美学值，并记录放置位置，完成一种方案就记录最大美学值和对应的摆放位置。

尽管知道会超时，先拿到部分分再说！

19分代码-DFS：

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int f, v;
int a[N][N];
int b[N]; //一个方案
int maxx = -2e9, ans[N]; //最大美学值，ans是最大美学值情况下每一朵花的方案

//考察第x朵花，前x-1朵花的美学值之和为sum
void dfs(int x, int sum)
{
    if(x > f)
    {
        if(sum > maxx)
        {
            maxx = sum;
            for(int i = 1; i <= f; i++) ans[i] = b[i]; //将b的方案拷贝到ans
        }
        return;
    }
    for(int i = b[x-1] + 1; i <= v; i++) //枚举第x朵花可以放置的花瓶，从第x-1朵花放置的花瓶数+1开始
    {
        b[x] = i; //把第x朵花放入i花瓶
        dfs(x + 1, sum + a[x][i]);
        b[x] = 0; //回溯
    }
}

int main()
{
    cin >> f >> v;
    for(int i = 1; i <= f; i++)
        for(int j = 1; j <= v; j++)
            cin >> a[i][j];

    dfs(1, 0);
    cout << maxx << endl;
    for(int i = 1; i <= f; i++) cout << ans[i] << " ";
    
    return 0;
}

如何对DFS代码进行优化，想到了记忆化搜索+剪枝，这里有一个特点：

对于每一朵花，枚举放置的位置一定是越来越靠后，而每朵花前面放置时的美学值如果比后面放置时的美学值大，那么后面的dfs可以提前结束，

因为再考察下去也无法得到最大美学值。

因此，可以记录mem[第x朵花][第x-1朵花的花瓶] = 考察第x朵花且已知第x-1朵花放置的花瓶时的美学值之和

100分代码-DFS+记忆化+剪枝：

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int f, v;
int a[N][N];
int b[N]; //一个方案
int mem[N][N]; //mem[i][j]记录第i朵花，第i-1朵花放置的花瓶是j时的美学值之和
int maxx = -0x3f3f3f3f, ans[N]; //最大美学值，ans是最大美学值情况下每一朵花的方案

//考察第x朵花，前x-1朵花的美学值之和为sum
void dfs(int x, int sum)
{
    if(sum <= mem[x][b[x-1]]) return; //如果当前sum比之前记录的要小或相等，不用继续dfs，提前结束
    mem[x][b[x-1]] = sum; //记录第x朵花 第x-1花放置的花瓶位置 对应的美学值之和
    if(x > f)
    {
        if(sum > maxx)
        {
            maxx = sum;
            for(int i = 1; i <= f; i++) ans[i] = b[i]; //将b的方案拷贝到ans
        }
        return;
    }
    for(int i = b[x-1] + 1; i <= v; i++) //枚举第x朵花可以放置的花瓶，从第x-1朵花放置的花瓶数+1开始
    {
        b[x] = i; //把第x朵花放入i花瓶
        dfs(x + 1, sum + a[x][i]);
        b[x] = 0; //回溯
    }
}

int main()
{
    cin >> f >> v;
    for(int i = 1; i <= f; i++)
        for(int j = 1; j <= v; j++)
            cin >> a[i][j];

    memset(mem, -0x3f, sizeof(mem));
    dfs(1, 0);
    cout << maxx << endl;
    for(int i = 1; i <= f; i++) cout << ans[i] << " ";
    
    return 0;
}

本题正解应该是动态规划，

设dp[i][j]表示前i朵花放入前j个花瓶的最大美学值, a[i][j]是第i朵花放入j号花瓶的美学值

当i放入j：dp[i][j] = dp[i-1][j-1] + a[i][j]

当i不放入j：dp[i][j] = dp[i-1][j]

因此：dp[i][j] = max(dp[]i-1[j], dp[i-1][j-1] + a[i][j])

初始化：

由于有负数，dp初始化为负无穷，memset(dp, -0x3f, sizeof(dp))；且dp[0][j]  = 0，前0朵花的美学值是0。

结果：dp[f][v]

记录具体方案:

用 struct node {

  vector<int> a;

   } ans[i][j] 记录前i朵花放入前j个花瓶得到最大美学值时的放置方案，

将转移方程dp[i][j] = max(dp[i][j-1], dp[i-1][j-1] + a[i][j])拆分为if...else...来分情况处理，记录放置方案的更新和转移，具体参考代码：

100分代码-动态规划：

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int f, v;
int a[N][N];
int dp[N][N]; //dp[i][j]表示前i朵花放入前j个花瓶的最大美学值
struct node 
{
    vector<int> a;
} ans[N][N]; //ans[i][j]记录前i朵花放入前j个花瓶得到最大美学值时的放置方案


int main()
{
    cin >> f >> v;
    for(int i = 1; i <= f; i++)
        for(int j = 1; j <= v; j++)
            cin >> a[i][j];
    
    memset(dp, -0x3f, sizeof(dp)); //初始化
    for(int j = 0; j <= v; j++) dp[0][j] = 0; //0朵花放j个花瓶的美学值是0

    for(int i = 1; i <= f; i++)
    {
        for(int j = i; j <= v; j++) //花瓶号不可能小于花的编号
        {
            if(dp[i-1][j-1] + a[i][j] > dp[i][j-1]) //第i朵花放第j个花瓶
            {
                dp[i][j] = dp[i-1][j-1] + a[i][j];
                //把i-1,j-1的方案拷贝到i,j的方案
                for(int v : ans[i-1][j-1].a)
                {
                    ans[i][j].a.push_back(v);
                }
                //i，j的方案再加上i放入第j个花瓶
                ans[i][j].a.push_back(j);
            }
            else //第i朵花不放第j个花瓶
            {
                dp[i][j] = dp[i][j-1];
                //把i,j-1的方案拷贝到i,j的方案
                for(int v : ans[i][j-1].a)
                {
                    ans[i][j].a.push_back(v);
                }
            }
        }
    }

    cout << dp[f][v] << endl;
    for(int v : ans[f][v].a) cout << v << " ";
    
    return 0;
}