题意简述
有一个正反面都为 \(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;
}