CodeForces 698A Vacations-白红宇

CodeForces 698A Vacations

阅读量：6189 次

发布时间：2019-06-21

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

简单$dp$。

记$dp[i][j]$表示$i$天过去了，并且第$i$天的时候是状态$j$的情况下，前$i$天最少休息天数。

递推式很容易得到：

$dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1$。

$if\left( {1\& a\left[ i \right]} \right)dp\left[ i \right]\left[ 1 \right] = min\left( {dp\left[ {i - 1} \right]\left[ 0 \right],dp\left[ {i - 1} \right]\left[ 2 \right]} \right)$。

$if\left( {2\& a\left[ i \right]} \right)dp\left[ i \right]\left[ 2 \right] = min\left( {dp\left[ {i - 1} \right]\left[ 0 \right],dp\left[ {i - 1} \right]\left[ 1 \right]} \right)$。

那么答案就是$min(dp[n][0],min(dp[n][1],dp[n][2]))$。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template 
               
                inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }}const int maxn=110;int a[maxn],dp[maxn][3],n;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[0][1]=dp[0][2]=dp[0][3]=1; for(int i=1;i<=n;i++) dp[i][1]=dp[i][2]=dp[i][3]=200; for(int i=1;i<=n;i++) { dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1; if(1&a[i]) dp[i][1]=min(dp[i-1][0],dp[i-1][2]); if(2&a[i]) dp[i][2]=min(dp[i-1][0],dp[i-1][1]); } printf("%d\n",min(dp[n][0],min(dp[n][1],dp[n][2]))); return 0;}

转载于:https://www.cnblogs.com/zufezzt/p/5801022.html

你可能感兴趣的文章