Codeforces Round #464 F. Cutlet

Description

题面

有$2*n$的时间,去煎一块肉,肉有两面,你需要在特定的时间内翻转,使得每一面都恰好煎了$n$分钟,你有$k$次翻转的机会,每一次表示为一段时间 $[L_i,R_i]$,你可以在区间内翻转任意次, 保证区间不相交

问是否存在合法的方案使得两面恰好都只煎了 $n$ 分钟,并输出最小翻转次数

$n<=100000,k<=100$

Solution

容易想到一个DP,设 $f[i][j]$ 表示一共煎了 $i$ 分钟,当前这一面煎了 $j$ 分钟的最小翻转次数

$f[i][j]=f[i-1][j]$

$f[i][j]=f[i-1][i-j]+1$

然后发现第二种转移只有在 $k$ 个区间内才会有,所以直接把第一维变成前 $i $ 个区间即可

容易发现:在一个区间内最多只会翻转两次,且某一面增加的时间的取值为 $[0,R_i-L_i]$

用单调队列维护这个DP即可

复杂度 $O(n*k)$

#include<bits/stdc++.h>

using namespace std;

const int N=200005,inf=2e8;

struct node{int l,r;}e[N];

int n,m,f[105][N],q[N],l,r;

inline void solve(int t){

	for(int i=0;i<=n;i++)f[t][i]=f[t-1][i];

	l=1;r=0;

	for(int i=0;i<=e[t].r;i++){

		while(l<=r && q[l]<i-(e[t].r-e[t].l))l++;

		if(l<=r)f[t][i]=min(f[t][i],f[t-1][q[l]]+2);

		if(i<=n){

			while(l<=r && f[t-1][i]<=f[t-1][q[r]])r--;

			q[++r]=i;

		}

	}

	l=1;r=0;q[++r]=0;

	for(int i=e[t].r;i>=0;i--){

		if(e[t].r-i<=n){

			while(l<=r && f[t-1][e[t].r-i]<=f[t-1][q[r]])r--;

			q[++r]=e[t].r-i;

		}

		while(l<=r && q[l]<e[t].l-i)l++;

		if(l<=r)f[t][i]=min(f[t][i],f[t-1][q[l]]+1);

	}

}

int main(){

  freopen("pp.in","r",stdin);

  freopen("pp.out","w",stdout);

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

  for(int i=1;i<=m;i++)scanf("%d%d",&e[i].l,&e[i].r);

  for(int i=1;i<=n;i++)f[0][i]=N;f[0][0]=0;

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

  if(f[m][n]<N)printf("Full\n%d\n",f[m][n]);

  else puts("Hungry");

  return 0;

}

巴特西

Codeforces Round #464 F. Cutlet

Description

Solution

最新文章

热门文章