标签：DP
题目
Description
圆桌上摆放着n份食物，围成一圈，第i份食物所含热量为c[i]。 相邻两份食物之间坐着一个人，共有n个人。每个人有两种选择，吃自己左边或者右边的食物。如果两个人选择了同一份食物，这两个人会平分这份食物，每人获得一半的热量。 假如某个人改变自己的选择后（其他n-1个人的选择不变），可以使自己获得比原先更多的热量，那么这个人会不满意。 请你给每个人指定应该吃哪一份食物，使得所有人都能够满意。
Input
第一行一个整数n(2<=n<=1000000)，表示食物的数量（即人数）。食物和人都从1~n编号。 第二行包含n个整数c[1],c[2],…,cn。 假设第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
分析
\(f[i][j]\)表示第i个食物，状态为j时的方案数，\(j\in [1,4]\)
- \(j=1\)表示食物被左边的人吃
- \(j=2\)表示食物被右边的人吃
- \(j=3\)表示食物不被人吃
- \(j=4\)表示食物被左右两人同时吃掉
转移的时候要写很多不同的条件，有点烦，摔）
时间复杂度为\(O(n)\)
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
const int maxn=1e6+6;
int c[maxn],f[maxn][6],ans[maxn],n;
int main()
{
n=read();
rep(i,0,n-1)c[i]=read();c[n]=c[0];
rep(i,1,4){
mem(f,0);
f[0][i]=1;
rep(j,1,n){
if(f[j-1][1]&&c[j]*2>=c[j-1])f[j][1]=1;
if(f[j-1][1]&&c[j]>=c[j-1])f[j][4]=1;
if(f[j-1][2]&&c[j-1]*2>=c[j])f[j][2]=2;
if(f[j-1][2]&&c[j-1]>=c[j])f[j][3]=2;
if(f[j-1][3]&&c[j]>=c[j-1])f[j][1]=3;
if(f[j-1][3]&&c[j]>=c[j-1]*2)f[j][4]=3;
if(f[j-1][4]&&c[j-1]>=c[j])f[j][2]=4;
if(f[j-1][4]&&c[j-1]>=c[j]*2)f[j][3]=4;
}
if(!f[n][i])continue;
for(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];
}
rep(j,1,n)cout<<ans[j]<<' ';cout<<endl;
return 0;
}
puts("NIE");
return 0;
}
