[POI2015] LAS

题目描述

题目传送门

思路

这题黑是恶意评分吧

考虑 dp，先想状态怎么设。

很容易想到的第一种 dp，假设 $dp_{i,j}$（$j \in \{1,2\}$），表示第 $i$ 个人吃了左边（$j = 1$）或者 右边（$j = 2$）的食物，可是这样似乎没有什么转移关系，所以做不了（或者我太菜了不会转移）。

既然这样状态做不了，考虑 dp 食物，假设 $dp_{i,j}$（$j \in \{1,2,3,4\}$），表示第 $i$ 食物被左边的人吃（$j = 1$）或者 被右边的人吃（$j = 2$）或者 被两边的人同时吃（$j = 3$）或者 不被吃（$j = 4$）。

考虑转移，对于这种初始状态不确定的，我们可以考虑强制确定第一个食物的状态，然后递推获得后面状态的可行性，并记录从那个状态转移过来，最后根据 dp 数组倒推得到答案。

讨论都很类似，在此仅讨论 $dp_{i,1}$ 的转移（$C$ 为热量数组）：

$$dp_{i,1} =\left\{ \begin{array}{lc} 1 \ \ \ \ \ C_{i-1} \le C_i \times 2 \\ 4 \ \ \ \ \ C_{i-1} \le C_i \ \ \ \texttt{如果同时满足上下两条条件取下面这条（贪心）} \end{array} \right.$$

代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

int N;
int Dp[MAXN][5] , Num[MAXN] , Ans[MAXN];

bool Dynamic_Programming(int s) {
	memset(Dp , 0 , sizeof Dp);
	Dp[1][s] = 1;
	for(int i = 2; i <= N + 1; i++) {
		if(Dp[i - 1][1] && Num[i - 1] <= Num[i] * 2) Dp[i][1] = 1;
		if(Dp[i - 1][1] && Num[i - 1] <= Num[i]) Dp[i][3] = 1;
		if(Dp[i - 1][2] && Num[i] <= Num[i - 1] * 2) Dp[i][2] = 2;
		if(Dp[i - 1][2] && Num[i] <= Num[i - 1]) Dp[i][4] = 2;
		if(Dp[i - 1][3] && Num[i] <= Num[i - 1]) Dp[i][2] = 3;
		if(Dp[i - 1][3] && Num[i] * 2 <= Num[i - 1]) Dp[i][4] = 3;
		if(Dp[i - 1][4] && Num[i - 1] <= Num[i]) Dp[i][1] = 4;
		if(Dp[i - 1][4] && Num[i - 1] * 2 <= Num[i]) Dp[i][3] = 4;
	}
	return Dp[N + 1][s];
}

int main() {
	scanf("%d" ,&N);
	for(int i = 1; i <= N; i++) {
		scanf("%d" ,Num + i);
	}
	Num[N + 1] = Num[1];
	for(int i = 1; i <= 4; i++) {
		if(Dynamic_Programming(i)) {
			int x = i;
			for(int j = N + 1; j >= 1; j--) {
				if(x == 1) {
					Ans[j - 1] = (j - 1) % N + 1;
				}
				if(x == 2) {
					Ans[j] = (j - 1) % N + 1;
				}
				if(x == 3) {
					Ans[j - 1] = Ans[j] = (j - 1) % N + 1;
				}
				x = Dp[j][x];
			}
			for(int i = 1; i <= N; i++) {
				printf("%d " ,Ans[i]);
			}
			return 0;
		}
	}
	return 0;
}