Sol
状态不好设, yzhx讲了才会
每一轮收银都会剩下一个人没有买单,也就是说,第x轮结束时在 [1, 2 * x - 1] 中将会有 x 人剩下
每次都转移被选中的两个人似乎不好搞,就看看能不能转移那个没被选中的人.
设 f[i][j] 表示第 i 次买单结束以后剩下了第 j 个人没有买单
那么枚举没有买单的那个人 j , 这一轮买单的第 2 \times i - 1 和 2 \times i 个人
注意到每次转移的时候 2 \times i - 1 和 2 \times i 个人也有可能是被选中的,也要转移
那么转移方程式是:
f[i][j] = min{ f[i-1][j] + max(t[a], t[b]) }
a, b 就是 2 \times i - 1 和 2 \times i
除此之外还要记一下方案
没了
Code
代码环节还是我最喜欢的环节
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 1e3 + 5;
const int inf = 0x7f7f7f7f;
int n;
int t[SIZE], f[SIZE][SIZE];
struct opt {
int i, j, k;
} path[SIZE][SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
inline void output(int i, int j)
{
if (i != 1) output(i - 1, path[i][j].k);
if (path[i][j].i > n) { printf("%lld\n", path[i][j].j); return; }
if (path[i][j].j > n) { printf("%lld\n", path[i][j].i); return; }
printf("%lld %lld\n", path[i][j].i, path[i][j].j);
}
signed main()
{
// freopen("code.in", "r", stdin);
// freopen("code.out", "w", stdout);
n = read();
for (int i = 1; i <= n; ++ i) t[i] = read();
t[++ n] = 0;
memset(f, inf, sizeof(f));
f[0][1] = 0;
for (int i = 1, a, b; i <= n / 2; ++ i) {
a = (i << 1), b = a + 1;
for (int j = 1; j < a; ++ j) {
if (f[i - 1][j] + std::max(t[a], t[b]) < f[i][j]) {
f[i][j] = f[i - 1][j] + std::max(t[a], t[b]);
path[i][j] = (opt) {a, b, j};
}
if (f[i - 1][j] + std::max(t[a], t[j]) < f[i][b]) {
f[i][b] = f[i - 1][j] + std::max(t[a], t[j]);
path[i][b] = (opt) {a, j, j};
}
if (f[i - 1][j] + std::max(t[b], t[j]) < f[i][a]) {
f[i][a] = f[i - 1][j] + std::max(t[b], t[j]);
path[i][a] = (opt) {b, j, j};
}
}
}
printf("%lld\n", f[n / 2][n]);
output(n / 2, n);
return 0;
}
Comments | NOTHING