题解 P1854 【花店橱窗布置】

Drifting · 2018-08-08 17:41:57 · 题解

欢迎访问博客，获得更佳阅读体验 戳这里

题面

洛谷 P1854

题目描述

某花店现有 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_{ij},它有 I 行，每行 J 个整数，A_{ij} 表示花束 I 摆放在花瓶 J 中的美学值。

输出格式

输出文件的第一行是一个整数，为最大的美学值；接下来有 F 行，每行两个数，为那束花放入那个花瓶的编号。

输入样例

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

输出样例

53
2 4 5

说明

感谢@罗恺提供SPJ

思路

读完题，你一定已经懵逼了。

没错，这种大赛的题目总是有着像语文/English 阅读理解的题面。

下面我来划一下重点：

给定一个 F \times J 的矩阵 A(F \leq J)，求一个序列 a_1,a_2,…,a_n 满足
使得 $A[1][a_1]+A[2][a_2]+…+A[n][a_n] $最大。矩阵中 $A_{ij}$ 可能含有负数。

很显然这是一道DP，然而，一样能把它看成是一道图论题。

把矩阵看成一张图的话，就是求从第 1 行到第 F 行的一条路径，使得路径上经过的点的权值最大。需要注意的是，从一个点出发，只能向它的右下移动，不能垂直向下或向左。

具体的做法，我们考虑设一个虚点 0，从 0 向第一行每个点连一条边，再从第一行开始向下一行的节点连边。

然后从 0 开始跑一个 SPFA 求出最长路，同时记录路径。

最后比较一下第 F 行每个点的 dis 值，最大的即为终点。从终点回溯，输出路径。

需要注意的是题目要求的路径是正序的，所以需要借助一个栈把路径正过来。

这种算法没有DP跑得快，但思路很显然很暴力。（毕竟不是标算嘛...）

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define trans(i, j) ((i - 1) * V + j)
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXF = 105;
const int MAXV = 105;
const int MAXN = MAXF * MAXV;
int cnt = 0, F, V, ma[MAXF][MAXV];
int head[MAXN], dis[MAXN + 1], pre[MAXN];
bool vis[MAXN + 1];
struct Edge
{
    int u, v, w, next;
} e[800000];
inline void add_Edge(int u, int v, int w)
{
    e[++cnt].u = u, e[cnt].v = v, e[cnt].w = w;
    e[cnt].next = head[u], head[u] = cnt;
}
void SPFA(int s)
{
    queue<int> q;
    for (int i = 1; i <= F * V; i++)
        dis[i] = -INF;
    dis[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v, w = e[i].w;
            if (dis[u] + w > dis[v])
            {
                dis[v] = dis[u] + w;
                pre[v] = u;
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d", &F, &V);
    for (int i = 1; i <= F; i++)
        for (int j = 1; j <= V; j++)
            scanf("%d", &ma[i][j]);
    for (int j = 1; j <= V; j++)
        add_Edge(0, trans(1, j), ma[1][j]);
    for (int i = 1; i < F; i++)
        for (int j = 1; j < V; j++)
            for (int k = j + 1; k <= V; k++)
                add_Edge(trans(i, j), trans(i + 1, k), ma[i + 1][k]);
    SPFA(0);
    int ans = -INF, end;
    for (int j = 1; j <= V; j++)
    {
        int u = trans(F, j);
        if (ans < dis[u])
            ans = dis[u], end = u;
    }
    printf("%d\n", ans);
    int sta[105];
    for (int i = F, j = end; i && j; j = pre[j], i--)
        sta[i] = j - (i - 1) * V;
    for (int i = 1; i <= F; i++)
        printf("%d ", sta[i]);
    return 0;
}