CodeForces 939F Cutlet

제목의 대의.

스테이크 한 조각은 양면 모두 N N N 초간 구워야 하는데, 지금은 K K 시간대 [L i, R i] [L i, R i] [Li, Ri]만 면을 뒤집을 수 있고, 이 시간 안에 이 스테이크를 마음대로 뒤집을 수 있다.
최소한 몇 번을 뒤집어서 스테이크 양쪽을 N, N, N 초간 구웠냐고.

분석하다.

신기한 DP.
정의 상태 f (i, j) f (i, j) f (i, j) 는 이전 i i 시간 동안 현재 위로 향하는 면이 j j 초의 최소 회전 횟수로 구워졌다.
상태 전환 방정식을 나열하는 것은 어렵지 않습니다.

우리가 뒤집지 않을 때: f(i, j)=f(i-3-1, j)f(i, j)=f(i-1, j)f(i, j)=f(i-31, j)=f(i-1, j);

우리가 한 번 뒤집을 때: f(i, j) = f(i-3, 1, i-3 j) + 1 f(i, j) = f(i-1, i-j) + 1 f(i, j) = f(i-3, 1, i-3 j) +1, 이 이전은 구간 [L i, R i] [L i, R i] [Li, Ri] 안에서만 발생한다.

분명히 이 이동은 O (N 2 K) O (N ^2 K) O (N 2 K) 이다.우리는 최적화를 고려해야 한다
결론: 우리가 한 구간에서 스테이크를 최대 두 번 뒤집을 때.
증명: 우리가 한 구간에서 세 번 이상의 스테이크를 뒤집을 때 우리는 단지 두 시간 간격으로 구운 스테이크의 면이 같다는 것을 발견할 수 있다. 그래서 우리는 등가의 교환 구간을 통해 스테이크의 뒤집는 횟수를 줄일 수 있다.
우리가 스테이크를 두 번 뒤집는 것은 다른 한 면만 한동안 구우기 위해서이며, 나올 때는 여전히 시작할 때의 한 면이다.이런 조작이 필요하다는 것을 증명할 수 있다.
우리가 한 번만 뒤집을 때 뒤집힌 후 양쪽에서 굽는 시간의 차이는 kk이고 뒤집는 시간은 jjj이다. 뒤집힌 후 위로 향하는 쪽의 굽는 시간은 Ri-3-jR 이다.i-j Ri -3. j, 아래 쪽으로 굽는 시간이 바로 R i -3. j -3. k Ri - j - k Ri​−j−k.
뒤집으면 양면이 서로 바뀌기 때문에 f(i, j) = min ⁡ {f(i-3, R i -3 j -3)} + 1 f(i, j) =\min\{f(i-1, R i -j-k)} + 1 f(i, j) = min {f(i -1, Ri -3 k)} +1이 있다.
의사결정의 단조성을 발견하기 어렵지 않기 때문에 단조로운 대열을 이용하여 의사결정점을 유지한다.
j+kj+kj+k를 직접 매거하는 것을 고려한 결과 이 이동은 거꾸로 매거해야 한다는 것을 발견했다.
우리가 두 번 뒤집었을 때 양면으로 굽는 시간 차이를 kk로 설정했는데 두 번 뒤집은 후에도 이 면이 아래로 향하기 때문에 f(i, j)=min⁡{f(i-1, j-k)}+2f(i, j-k)}=\min\f(i-1, j-k)\}+2f(i, j)=min{f(i, j)=min{f(i-1, j-k)+2}를 얻었다.
마찬가지로 단조로운 대열로 유지할 수 있지만, 이 이동은 일일이 열거해야 한다.
그러므로 전체 시간의 복잡도는 O(NK)O(NK)O(NK)이다.
그리고 공간이 터지지 않도록 스크롤 그룹을 열었습니다.

참조 코드

#include 
#include 
#include 
using namespace std;

const int Maxn = 200000;
const int Maxk = 100;
const int INF = 0x3f3f3f3f;

int N, K;
int L[Maxk + 5], R[Maxk + 5];

int f[2][Maxn + 5];

int q[Maxn + 5];

int main() {
#ifdef LOACL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d %d", &N, &K);
	for(int i = 1; i <= K; i++)
		scanf("%d %d", &L[i], &R[i]);
	memset(f[0], 0x3f, sizeof f[0]);
	f[0][0] = 0;
	int z = 1;
	for(int k = 1; k <= K; k++) {
		memcpy(f[z], f[z ^ 1], sizeof f[z]);
		int head = 1, tail = 0;
		for(int i = 0; i <= min(N, R[k]); i++) {
			while(head <= tail && f[z ^ 1][i] <= f[z ^ 1][q[tail]])
				tail--;
			q[++tail] = i;
			while(head <= tail && q[head] < i - (R[k] - L[k]))
				head++;
			f[z][i] = min(f[z][i], f[z ^ 1][q[head]] + 2);
		}
		head = 1, tail = 0;
		for(int i = R[k]; i >= 0; i--) {
			while(head <= tail && f[z ^ 1][R[k] - i] <= f[z ^ 1][q[tail]])
				tail--;
			q[++tail] = R[k] - i;
			while(head <= tail && q[head] < L[k] - i)
				head++;
			f[z][i] = min(f[z][i], f[z ^ 1][q[head]] + 1);
		}
		z ^= 1;
	}
	if(f[z ^ 1][N] >= INF) puts("Hungry");
	else printf("Full
%d
", f[z ^ 1][N]);
	return 0;
}