【貪心】Codeforces698A-Vacations

哎，這道題昨天上午學長講過思路，按照學長的想法寫好了程式就是不AC，真是￥%#……%&了，狠在那裡想貪心呢，後來看了其他菊苣的思路發現還要用到動态規劃……完全沒有聽說過好吧！？後來又搜了搜動态規劃，看看大神的代碼，搞了一上午才搞明白。。。不說廢話了，先上題！

【題目】

Vacations Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Description（描述）

Vasya has n days of vacations! So he decided to improve his IT skills and do sport. Vasya knows the following information about each of this n days: whether that gym opened and whether a contest was carried out in the Internet on that day. For the i-th day there are four options:

1. on this day the gym is closed and the contest is not carried out;
2. on this day the gym is closed and the contest is carried out;
3. on this day the gym is open and the contest is not carried out;
4. on this day the gym is open and the contest is carried out.

On each of days Vasya can either have a rest or write the contest (if it is carried out on this day), or do sport (if the gym is open on this day).

Find the minimum number of days on which Vasya will have a rest (it means, he will not do sport and write the contest at the same time). The only limitation that Vasya has — he does not want to do the same activity on two consecutive days: it means, he will not do sport on two consecutive days, and write the contest on two consecutive days.

Input（輸入要求）

The first line contains a positive integer n (1 ≤ n ≤ 100) — the number of days of Vasya's vacations.

The second line contains the sequence of integers a1, a2, ..., an (0 ≤ ai ≤ 3) separated by space, where:

• ai equals 0, if on the i-th day of vacations the gym is closed and the contest is not carried out;
• ai equals 1, if on the i-th day of vacations the gym is closed, but the contest is carried out;
• ai equals 2, if on the i-th day of vacations the gym is open and the contest is not carried out;
• ai equals 3, if on the i-th day of vacations the gym is open and the contest is carried out.

Output（輸出要求）

Print the minimum possible number of days on which Vasya will have a rest. Remember that Vasya refuses:

• to do sport on any two consecutive days,
• to write the contest on any two consecutive days.

Sample Input（樣例輸入）

Input 4

1 3 2 0 Output 2 Input 7

1 3 3 2 1 2 3 Output 0 Input 2

2 2 Output 1

【題目解釋】

mdzz又是英文題！題目說有一個少年放假了閑着沒事幹，每天有三種活動可以選擇：去健身房，參加比賽，在家呆着。

ai = 0,表示第i天健身房不開門這天也沒有比賽可以參加；

ai = 1,表示第i天有比賽但是健身房關門；

ai = 2,表示第i天健身房開門但是沒有比賽；

ai = 3,表示第i天健身房開門，也有比賽可以參加。

但是有要求：任意連續的兩天不能連續健身或比賽。要求出這個boy在這個假期裡最少能在家呆上幾天（就是盡可能不在家呆着）。

第一行輸入假期天數，第二行通過0123分别代表每天能參加的活動情況，對應n個數字。第三行輸出答案。

【解題思路】

動态規劃：簡單來說就是根據前面已有的資料來推後面，這種方法要求後面的東西不能影響到前面。

貪心：隻考慮眼前的最優解。

這裡貪心算法跟動态規劃結合，我們設定數組a[102]（題目上說了假期最多100天，多設兩個安全點）來儲存每天能參加的活動（0123），再設定一個dp[ i ][ 4 ]的二維數組，dp[ i ][ 0 ]中儲存的事如果第i天boy做了第0件事，那麼截止至第i天，這個boy已經在家呆了的天數。我們設定dp[ 0 ][ 0 ]dp[ 0 ][ 1 ]dp[ i ][ 2 ]dp[ 0 ][ 3 ]為0，因為第0天啥也不是沒什麼意義，其它的元素全部初始化為一個很大的數（這個數值一定要超過假期總天數，後面會解釋）。

這樣到第i天時，如果這天活動是第0号活動，那麼今天必然呆在家，那麼dp[ i ][ 0 ]就是直到昨天那一天一共休息的最少天數加1，即dp[ i ][ 0 ]為dp[ i-1 ][ 0 ]dp[ i-1 ][ 1 ]dp[ i-1 ][ 2 ]dp[ i-1 ][ 3 ]中的最小值加1，可能有人會疑問，dp[ i ][ 1 ]dp[ i ][ 2 ]dp[ i ][ 3 ]的值還沒有設定啊，它們初始化之後數值不是很大嗎？我們知道這個時候我們沒辦法執行123号情況，那麼這三個數就成了無用值，不在我們後面計算天數的範圍之内了，設定為大于假期的數，在最後考慮的時候就能直接發現并舍去了，執行後面123号操作時，沒有考慮的dp[ i ][ j ]值也是這個原理。

如果是一号活動，就有兩種情況： 執行0或者1， 如果執行0，此時dp[ i ][ 0 ]的值同第0号活動計算的方式相同，即dp[ i ][ 0 ]就是昨天一天休息的最少天數加1，若執行1，那麼dp[ i ][ 1 ]（注意是dp[ i ][ 1 ]不是dp[ i ][ 0 ]！）就等于直到昨天那一天一共休息了的最少天數（此時不在家是以不加1），即dp[ i ][ 1 ]為dp[ i-1 ][ 0 ]dp[ i-1 ][ 2 ]dp[ i-1 ][ 3 ]中的最小值（這裡沒有出現dp[ i-1 ][ 1 ]，因為他要做的活動不會跟前一天的一樣！）；2号活動時方式同一号，三号活動是1号和2号的綜合，即3号活動時，他可以選擇去做0、1、2中的任何一種，計算這三種情形下的天數就行了，方式跟前面一樣。

這樣直到最後的第n天時，會出現如果此時選擇0、1、2、3号活動時，休息的總天數。這樣把p[ n ][ 0 ]、dp[ n ][ 1 ]、dp[ n ][ 2 ]三個數一比較，找到其中最小值就是我們要的答案了~這個了解起來确實很難，自己可以動手畫一下，思路就會比較清晰了。按照上面的分析再看一看下面的代碼，應該就好了解了。

【代碼】

#include
   
    
#include
    
     
#include
     
      
using namespace std;
int main()
{
	int a[102]={0};
	int n;
	while(~scanf("%d",&n))
	{
		int ans=0;
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		int dp[102][4];
		memset(dp,1,sizeof(dp));
		dp[0][0]=dp[0][1]=dp[0][2]=dp[0][3]=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==0)
			{
				dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
			}
			if(a[i]==1)
			{
				dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
				dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
			}
			if(a[i]==2)
			{
				dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
				dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
			}
			if(a[i]==3)
			{
				dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1;
				dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
				dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
			}
		}
		ans=min(dp[n][0],min(dp[n][1],dp[n][2]));
		printf("%d\n",ans);	
	}
}