传送门：https://www.luogu.org/problem/P3584
据说对人设状态会很复杂，所以就针对食物来设置状态
f[i][0/1/2/3]分别表示不被吃/被左吃/被右吃/被都吃
接下来看转移方程（依据是，在什么情况下前面那个人会最初当前选择，而不选别的选择显然是当前最优，更改后不会更优啊）
最后因为是环，所以我们先枚举第一个食物的状态，然后看最后这个状态是否是最优状态(即是否合法)
//代码巨丑... #include<cstdio> #include<cstring> #define R register typedef long long ll; using namespace std; int n,c[1001000]; int f[1001000][4],ans[1001000];// 0_none 1_left 2_right 3_both int main () { scanf("%d",&n); for(R int i=1;i<=n;i++) scanf("%d",&c[i]); c[0]=c[n];c[n+1]=c[1]; for(R int i=0;i<=4;i++){ memset(f,-1,sizeof(f)); f[1][i]=i; for(R int j=2;j<=n+1;j++){ if(f[j-1][3]!=-1&&c[j-1]>=c[j]<<1) f[j][0]=3; if(f[j-1][2]!=-1&&c[j-1]>=c[j]) f[j][0]=2; if(f[j-1][1]!=-1&&c[j]<<1>=c[j-1]) f[j][1]=1; if(f[j-1][0]!=-1&&c[j]>=c[j-1]) f[j][1]=0; if(f[j-1][2]!=-1&&c[j]<=c[j-1]<<1) f[j][2]=2; if(f[j-1][3]!=-1&&c[j]<=c[j-1]) f[j][2]=3; if(f[j-1][0]!=-1&&c[j]>=c[j-1]<<1) f[j][3]=0; if(f[j-1][1]!=-1&&c[j]>=c[j-1]) f[j][3]=1; } if(f[n+1][i]!=-1){ int k=i; for(R int j=n;j>=1;j--){ if(k==1) ans[j]=j%n+1; else if(k==2) ans[j%n+1]=j%n+1; else if(k==3) ans[j]=ans[j%n+1]=j%n+1; k=f[j+1][k]; } for(R int j=1;j<=n;j++) printf("%d ",ans[j]); return 0; } } printf("NIE"); return 0; }
原文：https://www.cnblogs.com/coclhy/p/11633401.html
