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
%d
",f[m][n]);
  else puts("Hungry");
  return 0;
}