DP怎么能学好呢(允悲

题目描述

某花店现有$F$束花，每一束花的品种都不一样，同时至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，从左到右按$1$到$V$顺序编号，$V$是花瓶的数目。花束可以移动，并且每束花用$1$到$F$的整数标识。如果$I < J$，则花束$I$必须放在花束$J$左边的花瓶中。例如，假设杜鹃花的标识数为$1$，秋海棠的标识数为$2$，康乃馨的标识数为$3$，所有花束在放入花瓶时必须保持其标识数的顺序，即杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶只能放一束花。

每个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为$0$。在上述的例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下的表格来表示：

花瓶$1$ 花瓶$2$ 花瓶$3$ 花瓶$4$ 花瓶$5$

杜鹃花 $7\ 23\ -5\ -24\ 16$

秋海棠 $5\ 21\ -4\ 10\ 23$

康乃馨 $-21\ 5\ -4\ -20\ 20$

根据表格，杜鹃花放在花瓶$2$中，会显得非常好看，但若放在花瓶$4$中，则显得很难看。

为了取得最佳的美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。

输入格式

输入文件的第一行是两个整数$F$和$V$，分别为花束数和花瓶数（$1≤F≤100$，$F≤V≤100$）。接下来是矩阵$A_{i,j}$,它有$I$行，每行$J$个整数，$A_{ij}$表示花束$I$摆放在花瓶$J$中的美学值。

输出格式

输出文件的第一行是一个整数，为最大的美学值；接下来$1$行$F$个数,第$J$个数代表第$J$束花放在了哪个瓶子里。

题解

这道题类似于$P2066$机器分配,不同的是这里每一朵花都是有编号的,而且必须按顺序放,这就意味着第$I$朵花只能放在第$I$到第$V$个瓶子里,因为前面的花都必须放好了才能放这一朵.我们有两种思路

思路一

既然这道题类似于机器分配,那么我们是不是可以真的按照机器分配来做呢?设$f[i][j]$表示前$i$朵花放在前$j$个瓶子里的最大美学价值.接下来我们考虑子问题之间的转移.

在放第$i$朵花之前,我们要知道,第$i$朵花只能放在第$i-1$朵花的后面.因此我们要枚举第$i$朵花的可能的位置,就从$i$到$j$之间循环枚举.即:
$$
f[i][j] = max(f[i][j],f[i-1][k] + a[i][j]),i\le k\le j
$$
因为美学价值是可能是负的,所以我们需要将$f$数组初始化为$-inf$,然后$f[0][0]=0$.

思路二

事实上还有一种方法来描述$f$数组,那就是设$f[i][j]$表示将第$i$朵花放在第$j$个花瓶中的最大美学价值.这时候,我们相当于硬点第$i$朵花放在第$j$个瓶子,因此我们枚举上一朵花的位置来转移.上一朵花可能放在区间$[i-1,j-1]$中.转移方程就是:
$$
f[i][j] = max(f[i][j],f[i-1][k])+a[i][j],i-1\le k\le j-1
$$
同样,我们需要初始化$f$数组为$-inf$,$f[0][0]=0$.

如何输出任意一组方案

上述两种思路都使用类似的方法来输出方案,即倒着扫描,找到在最后一朵花时推出最优解的是哪一个瓶子,然后递归往前找倒数第二朵花时是哪一个瓶子推出了最终答案减去最后一个瓶子的美学价值,然后递归往前…最后在递归回来的时候输出.

代码:

#include <cmath>
#include <queue>
#include <deque>
#include <cctype>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

template<class T> inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch))
        w = (ch =='-'), ch = getchar();
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int n, m, f[105][105], a[105][105];

void print(int now, int nowans) {
    if (!now)
        return;
    int t = now;
    while (f[now][t] != nowans)
        t++;
    print(now - 1, nowans - a[now][t]);
    cout << t << " ";
    return;
}

signed main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            read(a[i][j]);
    memset(f, 128, sizeof(f));
    f[0][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= m; ++j)
            for (int k = i - 1; k <= j - 1; ++k)
                f[i][j] = max(f[i - 1][k] + a[i][j], f[i][j]);
    int ans = 0;
    for (int i = n; i <= m; ++i)
        ans = max(ans, f[n][i]);
    cout << ans << endl;
    print(n, ans);
    return 0;
}