p3584 [POI2015]LAS-白红宇

p3584 [POI2015]LAS

阅读量：5901 次

发布时间：2019-06-19

本文共 1206 字，大约阅读时间需要 4 分钟。

分析

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

我们需要满足两个条件：

每个人只能选择一个

改变选择之后不会比当前获得热量多

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

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

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   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
                   
                    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