Codeforces Round #363 (Div. 2) C. Vacations —— DP

题目链接：http://codeforces.com/contest/699/problem/C

题解：

1.可知每天有三个状态：1.contest ，2.gym，3.rest。

2.所以设dp[i][j]（i:1~n，j:1~3）为第i天进行j活动的最小休息天数。

3.状态转移：

contest：如果当天可以进行，从上一天的gym和rest中转移过来，取最小值。否者置为无限大INF。

gym：如果当天可以进行，从上一天的contest和rest中转移过来， 取最小值。否则置为无限大INF。

rest：每一天都可以进行。 从上一天的contest、gym和rest中转移过来， 取最小值。

4.最后取第n天的三个状态的最小值即为答案。

代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <string>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <sstream>

#include <algorithm>

using namespace std;

#define pb push_back

#define mp make_pair

#define ms(a, b)  memset((a), (b), sizeof(a))

#define eps 0.0000001

typedef long long LL;

const int INF = 2e9;

const LL LNF = 9e18;

const int mod = 1e9+7;

const int maxn = 200000+10;

int n;

int a[1005], dp[1005][3];

int main()

{

    scanf("%d",&n);

    for(int i = 1; i<=n; i++)

        scanf("%d",&a[i]);

    for(int i = 1; i<=n; i++)//初始化为无限大， 表示当天不能进行此项活动。

    for(int j = 1; j<=3; j++)

        dp[i][j] = INF;

    dp[0][1] = dp[0][2] = dp[0][3] = 0;//第0天时，三种状态都为0。

    for(int i = 1; i<=n; i++)

    {

        if(a[i]%2) dp[i][1] = min( dp[i-1][2], dp[i-1][3] ); //contest

        if(a[i]/2) dp[i][2] = min( dp[i-1][1], dp[i-1][3] ); //gym

        dp[i][3] = min( dp[i-1][1], min(dp[i-1][2], dp[i-1][3]) ) + 1;

    }

    int ans = min( min(dp[n][1], dp[n][2]), dp[n][3] );

    printf("%d\n",ans);

    return 0;

}