题意简述

有一个正反面都为 \(0\) 的卡片，每过 \(1\) 分朝下那一面的数值就会增加 \(1\)，你可以在几个区间的时间内翻转卡片，求经过 \(2n\) 秒后能否让这个卡片的正反面的数都为 \(n\)，求最小翻转数。

暴力

为了简单起见，我们定义一面为正面，一面为反面，\(1\) 表示正面，\(0\) 表示反面。

一眼看出来 dp，\(dp_{i,j,1/0}\) 表示在第 \(i\) 个区间结束后，正面数字为 \(j\)，\(1/0\) 面朝上的最小翻转数。

那么状态转移方程为：

\(dp_{i,j,1}=\min(dp_{i-1,j-p,1}+2,dp_{i-1,j-q,0}+1,dp_{i-1,j-g,1})\)

\(dp_{i,j,0}=\min(dp_{i-1,j-p,1}+1,dp_{i-1,j-q,0}+2,dp_{i-1,j,0})\)

其中满足：

区间间隔 \(\le p \le\) 两个区间右端点间隔。

区间长度 \(\le q \le\) 两个区间右端点间隔。

\(g\) 表示两个区间右端点间隔。

不难发现，这样的转移是 \(O(n)\) 的，再加上我们需要计算 \(nk\) 个 dp 值，这样做显然超时。需要考虑优化。

优化

不难发现，在计算一个区间完成后的值时，如果我们从 \(n\) 到 \(0\) 来计算，每次计算值所需要遍历区间的上限和下限都时逐渐减少的，那么我们就可以采取单调队列优化了。

这里用到一个小技巧：

如果一开始遍历区间的下限不为最低，那么我们可以令一个变量 \(idx\) 一开始指向第一个区间的下限，然后逐渐降低，分批入队。

这个单调队列可以滚动掉一维，只需要保留它记录 dp 值的 \(0/1\) 就行了。

Code

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10, K = 110, INF = 0x3f3f3f3f; int dp[K][N * 2][2]; int g[K], n, k, idx[2]; deque <int> q[2]; struct line { int l, r; bool operator < (const line& rhs) const { return l < rhs.l; } }lines[K]; inline void q_push (int i, int j, int op) { while (q[op].size() && dp[i][q[op].back()][op] >= dp[i][j][op]) q[op].pop_back(); q[op].push_back(j); } inline void q_pop (int i, int j, int op) { while (q[op].size() && j - q[op].front() < 0) q[op].pop_front(); } inline void init () { q[1].clear(); q[0].clear(); idx[0] = idx[1] = 2 * n; } int main () { memset(dp, INF, sizeof(dp)); scanf("%d%d", &n, &k); for (int i = 1;i <= k;i++) scanf("%d%d", &lines[i].l, &lines[i].r); sort(lines + 1, lines + 1 + k); g[1] = lines[1].l; g[k + 1] = 2 * n - lines[k].r; for (int i = 2;i <= k;i++) g[i] = lines[i].l - lines[i - 1].r; for (int j = lines[1].l;j <= lines[1].r;j++) { dp[1][j][1] = 2; dp[1][j][0] = 1; } dp[1][lines[1].r][1] = 0; for (int i = 2;i <= k;i++) { int l = lines[i].r - lines[i - 1].r, lg = lines[i].r - lines[i].l; init(); for (int j = lines[i].r;j >= 0;j--) { while (j - l <= idx[1] && idx[1] > 0) q_push(i - 1, idx[1]--, 1); while (j - lg <= idx[0] && idx[0] > 0) q_push(i - 1, idx[0]--, 0); q_pop(i - 1, j - g[i], 1); q_pop(i - 1, j, 0); dp[i][j][1] = min(dp[i][j][1], (q[1].size() ? dp[i - 1][q[1].front()][1] + 2 : INF)); dp[i][j][1] = min(dp[i][j][1], (q[0].size() ? dp[i - 1][q[0].front()][0] + 1 : INF)); dp[i][j][1] = min(dp[i][j][1], (j - l >= 0 ? dp[i - 1][j - l][1] : INF)); // cout << i << " " << j << " 1: " << dp[i][j][1] << endl; } init(); for (int j = lines[i].r;j >= 0;j--) { while (j - l <= idx[1] && idx[1] > 0) q_push(i - 1, idx[1]--, 1); while (j - lg <= idx[0] && idx[0] > 0) q_push(i - 1, idx[0]--, 0); q_pop(i - 1, j - g[i], 1); q_pop(i - 1, j, 0); dp[i][j][0] = min(dp[i][j][0], (q[1].size() ? dp[i - 1][q[1].front()][1] + 1 : INF)); dp[i][j][0] = min(dp[i][j][0], (q[0].size() ? dp[i - 1][q[0].front()][0] + 2 : INF)); dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]); // cout << i << " " << j << " 0: " << dp[i][j][0] << endl; } } if (min(n - g[k + 1] >= 0 ? dp[k][n - g[k + 1]][1] : INF, dp[k][n][0]) < INF) printf("Full\n%d\n", min(n - g[k + 1] >= 0 ? dp[k][n - g[k + 1]][1] : INF, dp[k][n][0])); else printf("Hungry\n"); return 0; }

链接：https://www.dianjilingqu.com/622340.html