算法
这个题目有题意有点不清晰,实际上要保证所有的花都要插在花瓶中,我一开始认为有些花瓶中可以不用插入任何花,导致浪费了大量的时间。
弄清题意后,不难发现这个题目是一个LIS的一种变式题,考虑到题目要求解最小字典序,因此必须由f[i][j]到f[i + 1][j]的转移,然后从开头遍历得到最小字典序。
用f[i][j]表示考虑后i种花,并且插入到了第j个瓶子,得到的最大美观值。
有如下细节需要注意:
1.由于题目中存在负值,初始情况下所有的状态都要设置为-inf。
2.为了方便状态转移,需要预置f[m][i]。
3.循环书写过程中,要防止出现不存在的状态转移。
(三重循环) $O(n^3)$
时间复杂度
$O(n^3)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int f[N][N];
int a[N][N];
int m, n;
int main() {
cin >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// 考虑i - m号花束,第i个花束摆在了第j个位置
memset(f, 0xcf, sizeof f);
for (int i = 1; i <= n; i++)
f[m][i] = a[m][i];
for (int i = m - 1; i >= 1; i--)
for (int j = n; j >= 1; j--)
for (int k = j + 1; k <= n; k++)
f[i][j] = max(f[i + 1][k] + a[i][j], f[i][j]);
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res, f[1][i]);
cout << res << endl;
int start = 0;
for (int i = 1; i <= m; i++, start++) {
while (start < n && res != f[i][start])
start++;
cout << start << " ";
res -= a[i][start];
}
return 0;
}