题目描述

题目传送门

思路

这题黑是恶意评分吧

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

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

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

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

讨论都很类似,在此仅讨论 dpi,1dp_{i,1} 的转移(CC 为热量数组):

dpi,1={1     Ci1Ci×24     Ci1Ci   如果同时满足上下两条条件取下面这条(贪心)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;
}