跳转至

P6879 [JOI 2020 Final] 集邮比赛 3 / Collecting Stamps 3 题解

题意

有 \(n\) 个物品排成一圈，给定圆上每个物品于出发点 \(A\) 向顺时针方向的距离 \(p_i\)，以及圆的周长 \(C\)。第 \(i\) 个物品只能在 \(t_i\) 时刻及以前被收集到。你初始位于出发点 \(A\)，每秒可以移动 \(1\text m\)。问最多可以收集到多少个物品。

\(n\le 200\)； \(p_i,t_i,C\le 10^9\)；

题解

挺板的区间 DP。记 \(f_{l,r,k,0/1}\) 表示收集 \(l\) 到 \(r\) 中的 \(k\) 个物品，最终位于 \(l/r\) 处，所需的最短时间。分讨从 \(l,r-1\) 和 \(l+1,r\) 转移即可。

重点关注代码中处理环的写法以及转移顺序。

AC 代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cmath>
#include<cstring>
#define int long long
using namespace std;
const int N = 210;
const int INF = (int)0x3f3f3f3f3f3f3f3f;

int n, c;
int p[N], t[N];

int f[N][N][N][2];

inline int calc(int a, int b) {
    return min(abs(p[a] - p[b]), c - abs(p[a] - p[b]));
}

signed main() {

    cin >> n >> c;

    ++n;
    p[1] = 0;
    t[1] = -1;

    for(int i = 2; i <= n; i++) {
        cin >> p[i];
    }
    for(int i = 2; i <= n; i++) {
        cin >> t[i];
    }

    memset(f, 0x3f, sizeof(f));
    f[1][1][0][0] = f[1][1][0][1] = 0;

    for(int len = 1; len < n; len++) {
        for(int i = 1; i <= n; i++) {
            int i1 = (i - 2 + n) % n + 1;
            int j = (i + len - 2) % n + 1;
            int j1 = (i + len - 1) % n + 1;
            for(int k = 0; k <= n; k++) {
                bool t1 = f[i][j][k][0] + calc(i1, i) <= t[i1];
                bool t2 = f[i][j][k][1] + calc(i1, j) <= t[i1];
                bool t3 = f[i][j][k][1] + calc(j, j1) <= t[j1];
                bool t4 = f[i][j][k][0] + calc(i, j1) <= t[j1];
                f[i1][j][k + t1][0] = min(f[i1][j][k + t1][0], f[i][j][k][0] + calc(i1, i));
                f[i1][j][k + t2][0] = min(f[i1][j][k + t2][0], f[i][j][k][1] + calc(i1, j));
                f[i][j1][k + t3][1] = min(f[i][j1][k + t3][1], f[i][j][k][1] + calc(j, j1));
                f[i][j1][k + t4][1] = min(f[i][j1][k + t4][1], f[i][j][k][0] + calc(i, j1));
            }
        }
    }

    for(int ans = n; ans >= 0; ans--) {
        int res = INF;
        for(int i = 1; i <= n; i++) {
            res = min(res, min(f[i][(i + n - 2) % n + 1][ans][0], f[i][(i + n - 2) % n + 1][ans][1]));
        }
        if(res != INF) {
            cout << ans << endl;
            break;
        }
    }

    return 0;
}