[CF939F]Cutlet

タイトル
転送ドアto luogu
注記区間[l,r][l,r][l,r]は、時刻l l lから時刻r rまでの間で反転可能であることを意味する.時刻0 0 0から、時刻2 n 2 nが終了する.
構想
神題.人は私にばかになった.このd ptt dp状態は非常に牛バッチを定義する.
f(i,j)f(i,j)f(i,j)はr i r_を表すi ri時点では、火の中の面でj j j j秒焼いていないので、少なくとも何回か反転する必要があります.
第i i i区間に反転がないとすると、
f ( i , j ) = f ( i − 1 , j ) f(i,j)=f(i-1,j) f(i,j)=f(i−1,j)
i i番目の区間で1回反転したと仮定する.今は「正面」と称して焼かれています.r i r_まで「正面」i ri時刻は全部でr i−j r_を焼くi-j ri−j秒、i i i番目の区間でt t t秒が焼かれると、
f ( i , j ) = f ( i − 1 , r i − j − t ) + 1 ( 0 ≤ t ≤ r i − l i ) f(i,j)=f(i-1,r_i-j-t)+1\quad(0\le t\le r_i-l_i) f(i,j)=f(i−1,ri​−j−t)+1(0≤t≤ri​−li​)
i i番目の区間で2回反転したと仮定する.実は「裏」を出して焼いたのです.それで
f ( i , j ) = f ( i − 1 , j − t ) + 2 ( 0 ≤ t ≤ r i − l i ) f(i,j)=f(i-1,j-t)+2\quad(0\le t\le r_i-l_i) f(i,j)=f(i−1,j−t)+2(0≤t≤ri​−li​)
3回以上反転しますか?何の役にも立たないよ.私が唯一コントロールできるのは、この区間で、表裏がどのくらい焼いたかです.終了時、どちらが上向きになりますか.明らかに、1回の反転はすべての奇数回の反転に代わることができ、2回の反転はすべての偶数回の反転を完了する.
区間長は固定されており,明らかにスライド窓の問題であり,O(1)mathcal O(1)O(1)転移を達成した.そしてこのc o s ttt cost costはとても簡単です
コード#コード#
単調なキューを1回だけ作りたい場合は、2番目の転送式を書くことができます.
f ( i , r i − j ) = f ( i − 1 , j − t ) + 1 ( 0 ≤ t ≤ r i − l i ) f(i,r_i-j)=f(i-1,j-t)+1\quad(0\le t\le r_i-l_i) f(i,ri​−j)=f(i−1,j−t)+1(0≤t≤ri​−li​)
そして直接f f fを単調な列に投げ込んだ.

#include 
#include 
#include 
using namespace std;
typedef long long int_;
inline int_ readint(){
	int_ a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int infty = (1<<30)-1;
int q[100001], head, tail;
// dp[i][j]: r_i   ，          j  
//         
int dp[102][100001];

int main(){
	int n = readint(), T = readint();
	for(int j=1; j<=n; ++j)
		dp[0][j] = infty;
	for(int i=1,l,r; i<=T+1; ++i){
		if(i != T+1)
			l = readint(), r = readint();
		else l = r = n<<1; //        
		l = r-l; //     
		for(int j=0; j<=n; ++j)
			dp[i][j] = dp[i-1][j];
		head = 1, tail = 0; // Q.clear()
		for(int j=0; j<=n; ++j){
			while(head <= tail)
				if(dp[i-1][q[tail]] >= dp[i-1][j])
					-- tail; else break;
			q[++ tail] = j;
			while(q[head] < j-l) ++ head;
			dp[i][j] = min(dp[i][j],dp[i-1][q[head]]+2);
			if(0 <= r-j && r-j <= n)
				dp[i][r-j] = min(dp[i][r-j],dp[i-1][q[head]]+1);
		}
	}
	if(dp[T+1][n] == infty){
		puts("Hungry"); return 0;
	}
	puts("Full");
	printf("%d
",dp[T+1][n]);
	return 0;
}