题解 CF939F 【Cutlet】

我的[博客](http://redbag.pw/) [更好的阅读体验](http://redbag.pw/2018/02/25/939F-Cutlet-dp/) 考虑暴力， $dp_{i,j} $ 表示前$ i $秒，当前没在烤的面被烤过$j$ 秒，所需要的最少的翻面次数。 很显然 $$ dp_{i,j}=\min(dp_{i−1,j},dp_{i−1,j−1}+1) $$ 然而这个肯定会T掉。 不过很容易发现，只有 k段 $dp_{i,j}$ 能从 $ dp_{i−1,j−1}$ 转移，于是我们可以优化。 $ f_{i,j} $ 表示在第 $ R_i $ 秒，目前没在烤的面烤了 $ j $秒，需要翻面的最小次数 $f_{i,j}=min(f_{i−1,j−k})+2 (0≤k≤ri−li)$ 翻过去烤k秒再翻回来 $f_{i,j}=min(f_{i−1,ri−j−k})+1 (0≤k≤ri−li) $ 当前面烤了 $r_{i}−j$ 秒，相当于某个时刻翻过来继续烤了 k 秒。 然后可以用单调队列优化（单调队列维护最值，见[另一篇文章](http://redbag.pw/2017/12/03/USACO12MAR-花盆Flowerpot-单调队列-二分/)） ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; void qmax(int &x,int y) {if (x<y) x=y;} void qmin(int &x,int y) {if (x>y) x=y;} inline int read() { char s; int k=0,base=1; while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s))); if(s==EOF)exit(0); if(s=='-')base=-1,s=getchar(); while(isdigit(s)){k=k*10+(s^'0');s=getchar();} return k*base; } inline void write(int x) { static char cnt,num[15];cnt=0; if (!x) { putchar('0'); return; } for (;x;x/=10) num[++cnt]=x%10; for (;cnt;putchar(num[cnt--]+48)); } const int maxn=2e5+10; const int maxk=110; int n,k; int L[maxk],R[maxk]; int dp[maxk][maxn]; struct node { int l,r; int q[maxn]; void clean() { l=1;r=0; memset(q,0,sizeof(q)); } void insert(int x,int y) { while (l<=r&&dp[x][q[r]]>=dp[x][y]) r--; r++;q[r]=y; } } a,b; int main() { n=read();k=read(); for (int i=1;i<=k;i++) L[i]=read(),R[i]=read(); memset(dp,0x3f3f3f3f,sizeof(dp)); dp[0][0]=0; for (int i=1;i<=k;i++) { a.clean(); for (int j=0;j<=n;j++) dp[i][j]=dp[i-1][j]; for (int j=0;j<=n;j++) { a.insert(i-1,j); while (a.l<=a.r&&a.q[a.l]<j-R[i]+L[i]) a.l++; qmin(dp[i][j],dp[i-1][a.q[a.l]]+2); } b.clean(); int Min=max(R[i]-n,0); int l1=L[i]+1,r1=R[i]+1; for (int j=R[i];j>L[i];j--) b.insert(i-1,j); for (int j=0;j<=n;j++) { l1--; r1--; while (b.l<=b.r&&b.q[b.l]>r1) b.l++; if (l1>=0) b.insert(i-1,l1); if (b.l<=b.r) qmin(dp[i][j],dp[i-1][b.q[b.l]]+1); } } if (dp[k][n]<=2333) printf("Full\n%d\n",dp[k][n]); else printf("Hungry"); return 0; } ```