題意簡述

有一個正反面都為?\(0\)?的卡片，每過?\(1\)?分朝下那一面的數(shù)值就會增加?\(1\)，你可以在幾個區(qū)間的時間內(nèi)翻轉(zhuǎn)卡片，求經(jīng)過?\(2n\)?秒后能否讓這個卡片的正反面的數(shù)都為?\(n\)，求最小翻轉(zhuǎn)數(shù)。

暴力

為了簡單起見，我們定義一面為正面，一面為反面，\(1\)?表示正面，\(0\)?表示反面。

一眼看出來 dp，\(dp_{i,j,1/0}\)?表示在第?\(i\)?個區(qū)間結(jié)束后，正面數(shù)字為?\(j\)，\(1/0\)?面朝上的最小翻轉(zhuǎn)數(shù)。

那么狀態(tài)轉(zhuǎn)移方程為：

\(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})\)

其中滿足：

區(qū)間間隔?\(\le p \le\)?兩個區(qū)間右端點間隔。

區(qū)間長度?\(\le q \le\)?兩個區(qū)間右端點間隔。

\(g\)?表示兩個區(qū)間右端點間隔。

不難發(fā)現(xiàn)，這樣的轉(zhuǎn)移是?\(O(n)\)?的，再加上我們需要計算?\(nk\)?個 dp 值，這樣做顯然超時。需要考慮優(yōu)化。

優(yōu)化

不難發(fā)現(xiàn)，在計算一個區(qū)間完成后的值時，如果我們從?\(n\)?到?\(0\)?來計算，每次計算值所需要遍歷區(qū)間的上限和下限都時逐漸減少的，那么我們就可以采取單調(diào)隊列優(yōu)化了。

這里用到一個小技巧：

如果一開始遍歷區(qū)間的下限不為最低，那么我們可以令一個變量?\(idx\)?一開始指向第一個區(qū)間的下限，然后逐漸降低，分批入隊。

這個單調(diào)隊列可以滾動掉一維，只需要保留它記錄 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