神奇的$dp$
按照每个人的选择设计状态是不可行的
考虑按照食物设计状态
$f[i][S](S∈[0,4])$表示第$i$个食物没有被选/左边选/右边选/同时选的状态是由哪一个状态转移来的
我们需要满足两个条件：
- 每个人只能选择一个
- 改变选择之后不会比当前获得热量多
讨论$a_i$和$a_{i-1}$的大小关系进行转移
输出方案的时候由后向前推过去就好
像这样的环形$dp$，一般套路都是先固定第一个的状态进行$dp$，枚举第一个的不同情况就可以了
```
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e6+5;
int n,a[N],ans[N],f[N][4];//0:Á½±ß¶¼²»Ñ¡ 1:×ó±ß 2:ÓÒ±ß 3:Á½±ß¶¼Ñ¡
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline bool work(int k)
{
memset(f,-1,sizeof(f)); f[1][k]=1;
for (reg int i=2;i<=n;i++)
{
if (~f[i-1][2]&&a[i-1]>=a[i]) f[i][0]=2;
if (~f[i-1][3]&&a[i-1]>=a[i]*2) f[i][0]=3;
if (~f[i-1][0]&&a[i]>=a[i-1]) f[i][1]=0;
if (~f[i-1][1]&&a[i]*2>=a[i-1]) f[i][1]=1;
if (~f[i-1][2]&&a[i-1]*2>=a[i]) f[i][2]=2;
if (~f[i-1][3]&&a[i-1]>=a[i]) f[i][2]=3;
if (~f[i-1][0]&&a[i]>=a[i-1]*2) f[i][3]=0;
if (~f[i-1][1]&&a[i]>=a[i-1]) f[i][3]=1;
}
return ~f[n][k];
}
inline void print(int k)
{
--n;
for (reg int i=n;~i;i--)
{
if (k==1) ans[i]=i%n+1;
if (k==2) ans[i+1]=i%n+1;
if (k==3) ans[i]=ans[i+1]=i%n+1;
k=f[i+1][k];
}
for (reg int i=1;i<=n;i++) printf("%d ",ans[i]);
exit(0);
}
int main()
{
n=read();
for (reg int i=1;i<=n;a[i++]=read()); a[++n]=a[1];
for (reg int i=0;i<4;i++) if (work(i)) print(i);
puts("NIE");
return 0;
}
```