p3584 [POI2015]LAS

传送门

分析

$f [i] [S] (S \in [0, 4])表示第$

我们需要满足两个条件：

每个人只能选择一个
改变选择之后不会比当前获得热量多

讨论 $$a_i$和$a_{i-1}$的大小关系进行转移$

输出方案的时候由后向前推过去就好

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int c[1000100],dp[4][1000100],ans[1000100];
inline void go(int pre,int now){
    if(~dp[2][pre]&&c[pre]>=c[now])dp[0][now]=2;
      else if(~dp[3][pre]&&c[pre]>=c[now]*2)dp[0][now]=3;
    if(~dp[0][pre]&&c[pre]<=c[now])dp[1][now]=0;
      else if(~dp[1][pre]&&c[pre]<=c[now]*2)dp[1][now]=1;
    if(~dp[2][pre]&&c[pre]*2>=c[now])dp[2][now]=2;
      else if(~dp[3][pre]&&c[pre]>=c[now])dp[2][now]=3;
    if(~dp[0][pre]&&c[pre]*2<=c[now])dp[3][now]=0;
      else if(~dp[1][pre]&&c[pre]<=c[now])dp[3][now]=1;
}
int main(){
    int n,m,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&c[i]);
    for(k=0;k<4;k++){
      memset(dp,-1,sizeof(dp));
      dp[k][1]=4;
      for(i=1;i<n;i++)go(i,i+1);
      go(n,1);
      if(dp[k][1]!=4){
          int now=dp[k][1];
          for(i=n;i>0;i--){
            if(now==1||now==3)ans[(i-2+n)%n+1]=i;
            if(now==2||now==3)ans[i]=i;
            now=dp[now][i];
          }
          for(i=1;i<n;i++)printf("%d ",ans[i]);
          printf("%d
",ans[i]);
          return 0;
      }
    }
    puts("NIE");
    return 0;
}