[POI2015]Łasuchy

[POI2015]Łasuchy

题目大意：

圆桌上摆放着(n(nle10^6))份食物，围成一圈，第(i)份食物所含热量为(c_i)。

相邻两份食物之间坐着一个人，共有(n)个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。

假如某个人改变自己的选择后（其他(n-1)个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。

问是否存在能使所有人都满意的方案。若存在，请你给每个人指定应该吃哪一份食物。

思路：

动态规划。

(f[i][jin[1,4]])表示对于第(i)个食物，状态为(j)的方案数。其中(j=1)表示被左边的人吃，(j=2)表示被右边的人吃，(j=3)表示没有被吃，(j=4)表示被两个人吃。

转移的时候枚举当前状态和前一个点的状态，若不会更优则进行转移。

由于是一个环，因此将第(n)个食物拆成(0)和(n)两个食物。一开始枚举(0)的状态。DP之后判断一开始枚举到的状态到(n)处是否仍旧合法即可。

时间复杂度(mathcal O(n))。

源代码：

#include<cstdio>
#include<cctype>
#include<cstring>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=1e6+1;
int c[N],f[N][5],ans[N];
int main() {
	const int n=getint();
	for(register int i=0;i<n;i++) c[i]=getint();
	c[n]=c[0];
	for(register int i=1;i<=4;i++) {
		memset(f,0,sizeof f);
		f[0][i]=1;
		for(register int i=1;i<=n;i++) {
			if(f[i-1][1]&&c[i]*2>=c[i-1]) f[i][1]=1;
			if(f[i-1][3]&&c[i]>=c[i-1]) f[i][1]=3;
			if(f[i-1][2]&&c[i-1]*2>=c[i]) f[i][2]=2;
			if(f[i-1][4]&&c[i-1]>=c[i]) f[i][2]=4;
			if(f[i-1][2]&&c[i-1]>=c[i]) f[i][3]=2;
			if(f[i-1][4]&&c[i-1]>=c[i]*2) f[i][3]=4;
			if(f[i-1][1]&&c[i]>=c[i-1]) f[i][4]=1;
			if(f[i-1][3]&&c[i]>=c[i-1]*2) f[i][4]=3;
		}
		if(!f[n][i]) continue;
		for(register int j=n,k=i;j>=1;j--) {
			if(k==1||k==4) ans[j]=j%n+1;
			if(k==2||k==4) ans[j%n+1]=j%n+1;
			k=f[j][k];
		}
		for(register int i=1;i<=n;i++) {
			printf("%d%c",ans[i]," 
"[i==n]);
		}
		return 0;
	}
	puts("NIE");
	return 0;
}