CF82D Two out of Three

Link

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;
}