Yahoo Programming Contest 2019 D-Ears-白红宇

Yahoo Programming Contest 2019 D-Ears

阅读量：7117 次

发布时间：2019-06-28

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

题目大意

分析

我们不难整个线段可以被划分为5段

我们设路径到达的最左的地方是L,最右的地方是R

则这五段分别是0~L,L+1~S,S+1~T,T+1~R,R+1~N

最外面的两端不经过,所以花费为a[i]

S+1~T这一段只能通过奇数次,剩余两段只能通过偶数次

所以这三段的答案均与奇偶性有关系

因此我们可以得到dp[i][0/1/2/3/4]表示现在考虑到第i个点,这个点属于第1/2/3/4/5段时的最优解

转移非常简单，详见代码

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define int long longconst int inf = 1e16+7;int dp[200100][5],a[200100];inline int wh2(int x){ if(x==0)return 2; return x%2;}inline int wh1(int x){ if(x==0)return 1; return (x%2)^1;}signed main(){ int n,m,i,j,k; scanf("%lld",&n); for(i=1;i<=n;i++)scanf("%lld",&a[i]); for(i=1;i<=n;i++) for(j=0;j<5;j++) dp[i][j]=inf; for(i=0;i<5;i++)dp[0][i]=0; for(i=1;i<=n;i++){ int wh=dp[i-1][0]; dp[i][0]=wh+a[i]; wh=min(wh,dp[i-1][1]); dp[i][1]=wh+wh2(a[i]); wh=min(wh,dp[i-1][2]); dp[i][2]=wh+wh1(a[i]); wh=min(wh,dp[i-1][3]); dp[i][3]=wh+wh2(a[i]); wh=min(wh,dp[i-1][4]); dp[i][4]=wh+a[i]; } cout<
                   
                    <