bzoj 3749: [POI2015]Łasuchy

3749: [POI2015]Łasuchy

Time Limit: 10 Sec   Memory Limit: 64 MBSec   Special Judge Submit: 355   Solved: 136 [ Submit][ Status][ Discuss]

Description

圆桌上摆放着n份食物，围成一圈，第i份食物所含热量为c[i]。 相邻两份食物之间坐着一个人，共有n个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。 假如某个人改变自己的选择后（其他n-1个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。 请你给每个人指定应该吃哪一份食物，使得所有人都能够满意。

Input

第一行一个整数n(2<=n<=1000000)，表示食物的数量（即人数）。食物和人都从1~n编号。 第二行包含n个整数c[1],c[2],…,c[n](1<=c[i]<=10^9)。 假设第i个人(1<=i<n)左边是第i份食物，右边是第i+1份食物；而第n个人左边是第n份食物，右边是第1份食物。

Output

如果不存在这样的方案，仅输出一行NIE。 如果存在这样的方案，输出一行共n个整数，第i个整数表示第i个人选择的食物的编号。如果有多组这样的方案，输出任意一个即可。

Sample Input

5 5 3 7 2 9

Sample Output

2 3 3 5 1

每个食物有四种状态

①case=0：这个食物没人吃

②case=1：这个食物被左边人吃

③case=2：这个食物被右边人吃

④case=3：这个食物被两边人共享

那么就可以暴力枚举第一个食物的case然后递推就好了

pos[i][case]表示第i-1个食物的状态为pos[i][case]的情况下第i个食物的状态可以为case（也就是前驱）

注意是个环所以第pos[1][case]的前驱应该是第n个食物的状态

如果你枚举的当前第一个食物状态k合法（也就是说pos[1][k]存在前驱）就说明当前是个合法解

递推过程主要是通过当前两个食物的量来判定，程序里有

#include<stdio.h> #include<string.h> int a[1000005], ans[1000005], pos[1000005][4]; int main(void) { int n, i, k, now; while(scanf("%d", &n)!=EOF) { for(i=1;i<=n;i++) scanf("%d", &a[i]); a[n+1] = a[1]; for(k=0;k<=3;k++) { memset(pos, -1, sizeof(pos)); pos[1][k] = 233; for(i=2;i<=n+1;i++) { if(~pos[i-1][0]) { if(a[i]>=a[i-1]) pos[i][1] = 0; if(a[i]>=a[ i-1]*2) pos[i][3] = 0; } if(~pos[i-1][1]) { if(a[i]*2>=a[i-1]) pos[i][1] = 1; if(a[i]>=a[i-1]) pos[i][3] = 1; } if(~pos[i-1][3]) { if(a[i]*2<=a[i-1]) pos[i][0] = 3; if(a[i]<=a[i-1]) pos[i][2] = 3; } if(~pos[i-1][2]) { if(a[i]<=a[i-1]) pos[i][0] = 2; if(a[i]<=a[i-1]*2) pos[i][2] = 2; } } if(~pos[n+1][k]) { now = pos[n+1][k]; for(i=n;i>=1;i--) { if(now==1) ans[(i+n-2)%n+1] = i; if(now==2) ans[i] = i; if(now==3) ans[i] = i, ans[(i+n-2)%n+1] = i; now = pos[i][now]; } printf("%d", ans[1]); for(i=2;i<=n;i++) printf(" %d ", ans[i]); break; } } if(k==4) printf("NIE\n"); } return 0; }