P6879 [JOI 2020 Final] スタンプラリー 3
Solution
-
首先这是一道最优值问题,再根据数据范围 \(n\le 200\),那么正解可能会是 \(O(n^3)\) 的 DP。
-
根据题意,我们发现主角走过的雕像一定是个区间,可以考虑区间DP。
-
想一想我们需要知道什么,然后把它放到 DP 状态里面。我们需要知道主角走过的是哪段区间,以及当前的时间,那么主角当前位置如何确定呢,并不需要枚举区间中的每个点,因为,如果他已经走完一段区间并且停留在端点上,那他下一次要去的位置肯定在端点外的一格,不会停留在区间里面。因此我们只需要知道他当前在左端点还是右端点即可,这是区间 DP 的一个经典套路。
-
由于 \(T\le 10^9\),显然复杂度是和值域无关的,如果我们记录当前时间,那状态数肯定会炸。于是又有一个经典套路,DP 状态的值域和定义域互换。定义域就是当前时间,值域显然就是当前收集到的数量,原本是当前时间能收集到的最大数量,互换了之后,我们可以记录当前收集了多少个雕像,需要的最小时间。由于答案不会超过 \(n\),那么这样是可行的。
-
设 \(f_{l,r,k,0/1}\) 表示当前从原点出发,顺时针走过了 \(l\) 个雕像,逆时针走过了 \(r\) 个雕像,一共收集了 \(k\) 个雕像,当前位置在左端点还是右端点,的最小时间。
-
转移很简单,例如,\(f_{l,r,k,0}\to f_{l+1,r,k+[f_{l,r,k,0/1}+x_{l+1}-x_l\ \le \ t_{l+1}],0}+x_{l+1}-x_l\)。
-
状态数是 \(O(n^3)\) 的,转移是 \(O(1)\),于是时间复杂度 \(O(n^3)\)。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 2e2 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n;
ll L, x[N], t[N], dp[N][N][N][2]; // 0 左边,1 右边
int ans = 0;
void Min(ll &a, ll b) {a = min(a, b);}
int main() {
cin >> n >> L;
for (int i = 1; i <= n; i++) cin >> x[i];
x[n + 1] = L;
for (int i = 1; i <= n; i++) cin >> t[i];
memset(dp, 0x3f, sizeof(dp));
dp[0][0][0][0] = dp[0][0][0][1] = 0;
for (int l = 0; l <= n; l++) {
for (int r = 0; l + r <= n; r++) {
for (int k = 0; k <= l + r; k++) {
int tmp;
if (dp[l][r][k][0] != inf) {
tmp = (dp[l][r][k][0] + x[l + 1] - x[l]) <= t[l + 1];
Min(dp[l + 1][r][k + tmp][0], dp[l][r][k][0] + x[l + 1] - x[l]);
tmp = (dp[l][r][k][0] + L - x[n - r] + x[l]) <= t[n - r];
Min(dp[l][r + 1][k + tmp][1], dp[l][r][k][0] + L - x[n - r] + x[l]);
ans = max(ans, k);
}
if (dp[l][r][k][1] != inf) {
tmp = (dp[l][r][k][1] + x[n - r + 1] - x[n - r]) <= t[n - r];
Min(dp[l][r + 1][k + tmp][1], dp[l][r][k][1] + x[n - r + 1] - x[n - r]);
tmp = (dp[l][r][k][1] + L - x[n - r + 1] + x[l + 1]) <= t[l + 1];
Min(dp[l + 1][r][k + tmp][0], dp[l][r][k][1] + L - x[n - r + 1] + x[l + 1]);
ans = max(ans, k);
}
}
}
}
cout << ans << "\n";
return 0;
}
标签:P6879,int,ll,2020,dp,端点,区间,JOI,DP
From: https://www.cnblogs.com/chenwenmo/p/18527489