F. Cutlet
第一次接触这样的动规设计。有收获
首先，我们先简化一下问题：
- (k)((kleq100))个给定区间，给这(2n)个区间染色（(0)或(1)），规定相邻颜色断点必须在给定区间内，问是否有合法的方案使两种颜色格子数均为(n)，以及最少的断点。
考虑可行性：
不妨设计DP：(dp(i,j,op)|opin{0,1})指前(i)个格颜色(op)染了(j)个各种的最少断点。
那么，
- 若第(i)个格子不在给定区间内部，转移到(dp(i-1,j-1,op))；
- 若在给定区间，不妨设该区间编号为(k)。转移到(dp(l_k o i-1,j',op xor 1)+1)；
这样的做法的时间复杂度为(O(n^2k))。
接下来，认真思考，可以发现在题目中，断点仅存在于给定区间中。基于这个性质，我们可以重新构造一个更精简的状态。
不妨设：(dp(i,j,op)|opin{0,1})，代表前个给定区间染了(j)个格子的最少断点。
那么，我们考虑一个区间的断点数量：
- 没有断点；
- 有一个断点；
- 有两个断点；
- 有多于(2)个断点；
显然，多于(2)个断点的一定不可能成为最优解。
那么，我们就可以讨论断点个数即可。换言之，
- 当没有断点时，有(dp(i-1,j,op))。
- 有一个断点时，有(dp(i-1,j-k,op xor 1)+1| kleq j,0leq kleq r_i-l_i)；这里我们枚举断点。
- 有两个断点时，有(dp(i-1,j-k,op)+2| kleq j,0leq kleq r_i-l_i)；这里我们枚举中部的区间长度。
时间复杂度还是没有变化，但是我们已经有了可以用单调队列优化的雏形。
优化
[dp(i,j,op)=minegin{cases} & ext dp(i-1,j,op)\& ext dp(i-1,r_{i-1}-(j-k),op xor 1)+1 (kleq j,0leq kleq r_i-l_i)\& ext dp(i-1,j-k,op)+2 (kleq j,0leq kleq r_i-l_i)end{cases}
]
该式子第(i)项仅和第(i-1)项有密切关系。
我们换元：
[dp(i,j,op)=minegin{cases} & ext dp(i-1,j,op)\& ext dp(i-1,k,op xor 1)+1 (kgeq 0,r_{i-1}-jleq kleq r_{i-1}-(l_i+j-r_i))\& ext dp(i-1,k,op)+2 (kgeq 0,l_i+j-r_ileq kleq j)end{cases}
]
这种情况直接单调队列优化。
不过，这样的转移特别的的复复杂，细节极容易搞错。我们可以依照博弈问题改变一下状态表示：设(dp(i,j))指前(i)个区间，另一种颜色还需要(j)个格子染色。接下来，就优化掉了一维，较之前细节少多了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define RE register
#define CLR(x, y) memset(x,y,sizeof x)
#define FOR(i, x, y) for(RE int i=x;i<=y;++i)
#define ROF(i, x, y) for(RE int i=x;i>=y;--i)
#define int LL
using namespace std;
typedef long long LL;
const int MAXN = 100 + 5, TIME = 2e5 + 10;
template <class T> void read(T &x)
{
bool mark = false;
char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') mark = true;
for(x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
if(mark) x = -x;
}
int n, k, hh, tt, l[MAXN], r[MAXN], q[TIME], dp[2][TIME];
signed main()
{
read(n), read(k);
FOR(i, 1, k) read(l[i]), read(r[i]);
FOR(i, 0, TIME) dp[0][i] = dp[1][i] = TIME;
dp[0][0] = 0;
FOR(i, 1, k)
{
hh = 1, tt = 1;
FOR(j, 0, n) dp[i & 1][j] = dp[(i - 1) & 1][j];
FOR(j, 0, r[i] - min(r[i], n))
{
while(hh < tt && dp[(i - 1) & 1][q[tt - 1]] >= dp[(i - 1) & 1][j]) -- tt;
q[tt ++] = j;
}
ROF(j, min(r[i], n), 1)
{
while(hh < tt && q[hh] < l[i] - j) ++ hh;
if(hh < tt) dp[i & 1][j] = min(dp[i & 1][j], dp[(i - 1) & 1][q[hh]] + 1);
if(r[i] - j < n)
{
while(hh < tt && dp[(i - 1) & 1][q[tt - 1]] >= dp[(i - 1) & 1][r[i] - j + 1]) -- tt;
q[tt ++] = r[i] - j + 1;
}
}
hh = 1, tt = 2;
FOR(j, 1, n)
{
while(hh < tt && q[hh] < l[i] + j - r[i]) ++ hh;
if(hh < tt) dp[i & 1][j] = min(dp[i & 1][j], dp[(i - 1) & 1][q[hh]] + 2);
if(j < n)
{
while(hh < tt && dp[(i - 1) & 1][q[tt - 1]] >= dp[(i - 1) & 1][j + 1]) -- tt;
q[tt ++] = j + 1;
}
}
}
if(dp[k & 1][n] == TIME) puts("Hungry");
else printf("Full
%d
", dp[k & 1][n]);
return 0;
}
总结：
- 在没有认真分析问题的时候，连最基本的DP表示都没有想出来，这说明了要踏下心去认真分析；
- 有时代码细节过多，可能是算法不够精炼；
- DP中博弈简化。