题目描述

小 q 和他的老婆小 z 最近开了一家花店，他们准备把店里最好看的花都摆在橱窗里。

但是他们有很多花瓶，每个花瓶都具有各自的特点，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果。

为了使橱窗里的花摆放的最合适，他们得想个办法安排每种花的摆放位置。

可是因为小 q 和小 z 每天都太忙，没有时间设计橱窗里花的摆法，所以他们想让你帮他们求出花摆放的最大美观程度和每种花所放的位置。

每种花都有一个标识，假设杜鹃花的标识数为 1，秋海棠的标识数为 2，康乃馨的标识数为 3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：

杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。

如果花瓶的数目大于花束的数目。则多余的花瓶必须空置，且每个花瓶中只能放一束花。

每种花放在不同的瓶子里会产生不同的美观程度，美观程度可能是正数也可能是负数。

为取得最大美观程度，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值，并求出每种花应该摆放的花瓶的编号。

输入格式

第 1 行：两个整数 $F$ 和 $V$，表示共有 $F$ 种花，$V$ 个花瓶。

第 2 行到第 $F+1$ 行：每行有 $V$ 个数，表示花摆放在不同花瓶里的美观程度值 $value$。（美观程度和小于 $2^{31}$，美观程度有正有负）

输出格式

输出有两行：

第一行为输出最大美观程度和的值。

第二行有 $F$ 个数表示每朵花应该摆放的花瓶的编号。

若有多种方案，输出字典序较小的方案（美观程度不变的情况下，花尽量往前放）。

样例

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

53
2 4 5

样例解释

数据

• $F = 3$（3 种花）
• $V = 5$（5 个花瓶）

美观程度矩阵：

花 \ 花瓶	1	2	3	4	5
1 (杜鹃花)	7	23	-5	-24	16
2 (秋海棠)	5	21	-4	10	23
3 (康乃馨)	-21	5		-20	20

要求

• 花必须按编号顺序摆放（1 在 2 左边，2 在 3 左边）。
• 每个花瓶最多放一束花。
• 花瓶可以空置。
• 求最大美观程度和，并输出每朵花应放的花瓶编号（字典序最小）。

最优解

摆放方案：

• 花 1 放在花瓶 2 → 美观值 23
• 花 2 放在花瓶 4 → 美观值 10
• 花 3 放在花瓶 5 → 美观值 20

总和 = 23 + 10 + 20 = 53

其他方案比较

如果花 1 放在花瓶 1（7），花 2 放在花瓶 2（21），花 3 放在花瓶 5（20），总和 = 48 < 53。
如果花 1 放在花瓶 2（23），花 2 放在花瓶 3（-4），花 3 放在花瓶 5（20），总和 = 39 < 53。
等等。

字典序要求：在美观程度相同的情况下，花尽量往前放（即编号小的花尽量选择编号小的花瓶）。但本题最优解唯一。

数据范围

• $1 \le F \le V \le 100$
• 美观程度值在 int 范围内（有正有负）

算法分析

这是一个动态规划问题，类似于“将 $F$ 个有序物品放入 $V$ 个位置，每个位置最多放一个，且物品顺序必须保持，求最大总价值”。

状态定义

设 $dp[i][j]$ 表示将前 $i$ 种花放入前 $j$ 个花瓶（且第 $i$ 种花恰好放在第 $j$ 个花瓶）的最大美观程度和。

转移方程

第 $i$ 种花放在第 $j$ 个花瓶时，前 $i-1$ 种花必须放在前 $j-1$ 个花瓶中，且第 $i-1$ 种花放在某个位置 $k$，其中 $i-1 \le k \le j-1$。

因此：

$$dp[i][j] = \max_{i-1 \le k \le j-1} \{ dp[i-1][k] \} + value[i][j]$$

其中 $value[i][j]$ 表示第 $i$ 种花放在第 $j$ 个花瓶的美观值。

初始化

• $dp[1][j] = value[1][j]$，对 $1 \le j \le V$。
• 其他 $dp[i][j] = -\infty$。

优化

转移时需要求 $dp[i-1][k]$ 在区间 $[i-1, j-1]$ 的最大值，可以在遍历 $j$ 的过程中维护前缀最大值，将复杂度从 $O(F \times V^2)$ 降为 $O(F \times V)$。

输出方案

为了输出字典序最小的方案，我们需要记录转移路径。定义 $pre[i][j]$ 表示状态 $dp[i][j]$ 是由 $dp[i-1][pre[i][j]]$ 转移而来。

在求 $dp[i][j]$ 时，如果有多个 $k$ 都能得到相同最大值，选择最小的 $k$（即字典序更小，因为花 $i-1$ 的位置尽量靠前，那么花 $i$ 的位置也会相对靠前）。

最后从 $dp[F][j]$ 中找最大值（$F \le j \le V$），然后逆推路径。

字典序处理

题目要求“花尽量往前放”，即对于相同的总美观值，我们希望花的摆放位置编号尽可能小。
在动态规划时，如果多个 $k$ 得到相同的 $dp[i-1][k]$，我们选择最小的 $k$，这样花 $i-1$ 的位置更靠前，后续花的位置也更容易靠前。

在最后选择 $dp[F][j]$ 的最大值时，如果有多个 $j$ 得到相同的最大值，选择最小的 $j$（即最后一朵花尽量靠前），然后逆推回去。

实现步骤

1. 读入 $F, V$ 和美观值矩阵 $value[F][V]$。
2. 初始化 $dp$ 数组为负无穷，$dp[1][j] = value[1][j]$。
3. 对于 $i = 2$ 到 $F$：
   • 维护一个变量 $maxVal$ 和 $maxIdx$ 表示 $dp[i-1][k]$ 在 $k$ 从 $i-1$ 到 $j-1$ 的最大值及对应的最小 $k$。
   • 对于 $j = i$ 到 $V$（因为前 $i$ 朵花至少需要 $i$ 个花瓶）：
     • 更新 $maxVal$ 和 $maxIdx$（考虑新的 $k = j-1$）。
     • $dp[i][j] = maxVal + value[i][j]$，记录 $pre[i][j] = maxIdx$。
4. 在 $dp[F][j]$（$j = F$ 到 $V$）中找到最大值，如果有多个，选最小的 $j$。
5. 逆推路径，得到每朵花的花瓶编号，然后正序输出。

复杂度

• 时间复杂度：$O(F \times V)$
• 空间复杂度：$O(F \times V)$