CodeForces 698A Vacations

 

->题目链接

 

  可以用动态解决问题，题目求的是最少的休息天数，我们可以通过求最大的工作天数来的得到答案。

  用数组dp[ i ][ j ]记录到第 i 天为止Vasya最大的工作天数，j 的定义如下，

  对于第 i 天 ，

    • j=0，表示Vasya第 i 天休息，dp[ i ][0]就表示如果第 i 天休息的话，能得到的最大的工作天数（其它类似）。

    • j=1 ,  表示Vasya第 i 天参加contest。

    • j=2 ,  表示Vasya第 i 天去gym。

 

  那么，可以得到下面的状态转移方程。

    dp[ i ][ 0] =max( dp[ i-1 ][  j ] ), 0≤j≤2。

    如果第 i 天有contest，即 a_i=1或 a_i=3，那么到第 i 天为止Vasya最大的工作天数为前一天Vasya休息或着去gym获得的最大的工作天数+1，即dp[ i ][1]=max( dp[i-1][0], dp[ i-1 ][2] ) + 1。

    如果第 i 天gym开放，即 a_i=2或 a_i=3，那么到第 i 天为止Vasya最大的工作天数为前一天Vasya休息或着参加contest获得的最大的工作天数+1，即dp[ i ][1]=max( dp[i-1][0], dp[ i-1 ][1] ) + 1。

 

    这样，最后的答案为n - max( dp[ n ][  j ] ), 0≤j≤2。

 

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <functional>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <cstdio>
using namespace std;
#define IOS ios_base::sync_with_stdio(false)
#define TIE std::cin.tie(0)
#define MAX2(a,b) (a>b?a:b)
#define MAX3(a,b,c)  (a>b?(a>c?a:c):(b>c?b:c))
typedef long long LL;
typedef unsigned long long ULL;
const int INF=0x3f3f3f3f;
const double PI=4.0*atan(1.0);

int n,x,dp[105][3];
int main()
{
    while(~scanf("%d",&n)){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            dp[i][0]=MAX3(dp[i-1][0],dp[i-1][1],dp[i-1][2]);
            if(x==1||x==3) dp[i][1]=MAX2(dp[i-1][0],dp[i-1][2])+1;
            if(x==2||x==3) dp[i][2]=MAX2(dp[i-1][0],dp[i-1][1])+1;
        }
        printf("%d
",n-MAX3(dp[n][0],dp[n][1],dp[n][2]));
    }
    return 0;
}