CodeForces 939F Cutlet

洛谷题目页面传送门 & CodeForces题目页面传送门

题意见洛谷里的翻译。

这是一道毒瘤的div. 2 F，我是不可能比赛的时候做出来的。。。

（以下设两面都要煎\(n\)分钟，有\(m\)个可翻转时间区间，第\(i\)个为\([l_i,r_i]\)）

废话不多说，这题可以考虑DP。数据范围告诉我们标算大概是\(\mathrm{O}(nm)\)的，不难想到可以把一个可翻转区间和与之相邻的不可翻转区间当作一个整体作为阶段。设\(dp_{i,j}\)表示当前考虑到时刻\(l_{i+1}\)（那么这个阶段需要考虑的时间段就是\([l_i,l_{i+1}]\)，即可翻转区间\([l_i,r_i]\)加上不可翻转区间\([r_i,l_{i+1}]\)，特殊地，\(l_0=0,r_0=-1,l_{m+1}=2n\)），最后一刻煎的那一面一共煎了\(j\)秒，所需要翻的最少次数。那么目标就是\(dp_{m,n}\)。很显然，边界是\(dp_{0,j}=\begin{cases}+\infty&j\ne l_1\\0&j=l_1\end{cases}\)，因为前\(l_1\)秒是翻不了的。而转移的时候只需要考虑在\([l_i,l_{i+1}]\)里翻\(0,1,2\)次的情况即可，因为翻更多次都可以转化为翻\(1\)或\(2\)次（感性理解一下）。那么状态转移方程就出来了：

\[dp_{i,j}=\min\!\left(dp_{i-1,j-(l_{i+1}-l_i)},\min\limits_{k=l_i}^{r_i}\{dp_{i-1,l_i-(j-(l_{i+1}-k))}+1\},\min\limits_{k=l_i}^{r_i}\{dp_{i-1,j-(l_{i+1}-k)}+2\}\right)
\]

将上面那个式子去去括号变变形，得

\[dp_{i,j}=\min\!\left(dp_{i-1,j-l_{i+1}+l_i},\min\limits_{k=l_i-j+l_{i+1}-r_i}^{l_i-j+l_{i+1}-l_i}\{dp_{i-1,k}\}+1,\min\limits_{k=j-l_{i+1}+l_i}^{j-l_{i+1}+r_i}\{dp_{i-1,k}\}+2\right)
\]

不难发现，最外面的\(\min\)里有\(3\)部分，分别是翻\(0,1,2\)次的情况。翻\(0\)次的转移是\(\mathrm{O}(1)\)的，而另外\(2\)个是\(\mathrm{O}(n)\)的。朴素地转移总时间复杂度为\(\mathrm{O}\!\left(n^2m\right)\)，爆炸不多说。不难发现，在同一个阶段里，随着\(j\)的增加，翻\(1\)次的\(\min\)的上下界同时减少，翻\(2\)次的则同时增加。这\(2\)个都可以用单调队列来优化到每个阶段均摊\(\mathrm{O}(n)\)（一个倒着单调队列，一个正着），于是总共\(\mathrm{O}(nm)\)。（如果你想不到单调队列，也可以在到达一个阶段的时候，把上一个阶段的DP值打个ST表，或者线段树维护，但那都是带\(\log\)的，过不掉hhhh，所以只能单调队列）

对了，我的代码里还用了滚动数组优化了一下空间。（其实根本不用，\(\mathrm{O}(nm)\)的空间在CodeForces上应该是可以过的，但保险起见）

下面贴AC代码：

#include<bits/stdc++.h>

using namespace std;

const int inf=0x3f3f3f3f;

const int N=100000,M=100;

int n/*每面要煎的秒数*/,m/*可翻转区间数*/;

int l[M+1],r[M+1];//每个区间的左右端点

int dp[2][2*N+1];//dp[i][j]表示当前考虑到时刻l[i+1]，最后一刻煎的那一面一共煎了j秒，所需要翻的最少次数

int q[2*N],head,tail;//单调队列

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)scanf("%d%d",l+i,r+i);

	l[m+1]=2*n;//dp[m][j]应当考虑完整个2n秒的时间了

	memset(dp[0],0x3f,sizeof(dp[0]));//边界

	dp[0][l[1]]=0;//边界

	for(int i=1;i<=m;i++){

		int now=i&1,prv=!now;//滚动数组

		memset(dp[now],0x3f,sizeof(dp[now]));//初始化为inf

		for(int j=0;j<=2*n;j++)dp[now][j]=min(dp[now][j],j-l[i+1]+l[i]<0?inf:dp[prv][j-l[i+1]+l[i]]);//翻0次

		head=tail=0;//清空单调队列

		for(int j=max(0,l[i]-2*n+l[i+1]-r[i]);j<-2*n+l[i+1];j++){//翻1次，因为是倒着的，所以从2n开始

			while(head<tail&&dp[prv][q[tail-1]]>=dp[prv][j])tail--;

			q[tail++]=j;

		}

		for(int j=2*n;~j;j--){//翻1次，倒着单调队列

//			cout<<j<<":\t+1=\t"<<l[i]-j+l[i+1]-r[i]<<"~"<<-j+l[i+1]<<"\n";

			while(head<tail&&q[head]<l[i]-j+l[i+1]-r[i])head++;

			if(-j+l[i+1]>=0){

				while(head<tail&&dp[prv][q[tail-1]]>=dp[prv][-j+l[i+1]])tail--;

				q[tail++]=-j+l[i+1];

			}

			dp[now][j]=min(dp[now][j],head==tail?inf:dp[prv][q[head]]+1);

		}

		head=tail=0;//清空单调队列

		for(int j=max(0,-l[i+1]+l[i]);j<-l[i+1]+r[i];j++){//翻2次，因为是正着的，所以从0开始

			while(head<tail&&dp[prv][q[tail-1]]>=dp[prv][j])tail--;

			q[tail++]=j;

		}

		for(int j=0;j<=2*n;j++){//翻2次，正着单调队列

//			cout<<j<<":\t+2=\t"<<j-l[i+1]+l[i]<<"~"<<j-l[i+1]+r[i]<<"\n";

			while(head<tail&&q[head]<j-l[i+1]+l[i])head++;

			if(j-l[i+1]+r[i]>=0){

				while(head<tail&&dp[prv][q[tail-1]]>=dp[prv][j-l[i+1]+r[i]])tail--;

				q[tail++]=j-l[i+1]+r[i];

			}

			dp[now][j]=min(dp[now][j],head==tail?inf:dp[prv][q[head]]+2);

		}

//		for(int j=0;j<=2*n;j++)printf("dp[%d][%d]=%d\n",i,j,dp[now][j]);

	}

	printf(dp[m&1][n]<inf?"Full\n%d\n":"Hungry",dp[m&1][n]);//目标是dp[m][n]

	return 0;

}

巴特西

CodeForces 939F Cutlet

洛谷题目页面传送门 & CodeForces题目页面传送门

最新文章

热门文章