HNU软件能力实训4-12. 疫情期间

写在前面

你好！欢迎来到我的博客，希望我的思路能够帮到你！

问题描述

正值新冠疫情期间，阿迪没法返回学校学习，他希望通过参加一些比赛来提高一下编程技能，同时做做运动。他收集了接下来的 n 天里每一天的信息，包括健身房是否开放，或者互联网上是否有程序设计竞赛。

第 i 天可以有以下四种情况之一：

 - 该天健身房不开放，互联网上也没有竞赛
   
 - 该天健身房不开放，但互联网上有竞赛
   
 - 该天健身房开放，但互联网上没有竞赛
   
 - 该天健身房开放，互联网上也有竞赛

每天阿迪要么休息，要么编写程序（如果该天有竞赛），要么做运动（如果该天健身房开放）。

现在有一个限制条件：不能连续两天都去做运动，或者连续两天都编写程序。阿迪对自己要求很高，希望尽量多写程序或者多做运动，使得休息的天数尽量最少，求出这个天数。

输入形式

输入的第一行为一个正整数 n (1 ≤ n ≤ 100)，表示接下来的天数。

第二行为一个用空格分隔的整数序列 a₁、a₂、…、a_n（0 ≤ a_i ≤ 3），这里

• a_i=0，第 i 天健身房不开放，互联网上也没有竞赛

• a_i=1，第 i 天健身房不开放，但互联网上有竞赛

• a_i=2，第 i 天健身房开放，但互联网上没有竞赛

• a_i=3，第 i 天健身房开放，互联网上也有竞赛

输出形式

输入阿迪可能休息的最小天数。注意限制条件：

• 不能连续两天去做运动

• 不能连续两天编写程序

样例输入

【样例输入1】

4
1 3 2 0

【样例输入2】

7
1 3 3 2 1 2 3

【样例输入3】

2
2 2

样例输出

【样例输出1】

2

【样例输出2】

0

【样例输出3】

1

样例说明

在第一个样例中，阿迪在第一天编写程序，在第三天做运动，因此他仅有两天可以休息。

在第二个样例中，阿迪可以在第1、3、5、7天编写程序，其他天做运动，因此没有哪天休息。

在第三个样例中，阿迪可以在第1天或第2天做运动，但不能连续两天运动，因此他有一天休息。

解题思路

这道题是一个dp问题，还是延续之前的做法，将原问题分为集合的属性以及集合的划分。

集合：f[i][j]表示到第i天为止，且第i天做了j的休息天数

属性：min

集合的划分：第i天的前一天是第i-1天，第i-1天我们可以休息，编程或者健身，那么我们就可以由第i-1天的情况来推出第i天的情况。

但是需要注意的是，由于会出现冲突问题，且我们知道第i天做了什么，所以我们要根据第i天做的东西，分类的选取第i-1天的方案进行递推

最后的状态转移方程就是：f[i][j]=min(f[i-1][0],f[i-1][1],f[i-1][2])

最后，不要问我为什么没有f[i-1][3]，3这种情况可以分到1和2里面

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=110,inf=0x3f3f3f3f;
int n;
int f[N][3];

//f[i][j]表示到第i天为止且第i天做了j的最小休息天数

int main()
{
	//输入
    cin>>n;
    
    //初始化每种方案为不存在
	memset(f,inf,sizeof f);
	
	//如果只有0天，不管怎么样都没得休息
    f[0][0]=f[0][1]=f[0][2]=0;
    
    //dp
    int x;
    for(int i=1;i<=n;i++)//由于有下标-1的操作，所以我们从1开始
    {
        cin>>x;//输入今天做了什么
        f[i][0]=min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+1;//今天休息的话，昨天干什么都可以，这种情况必定存在，不需要判断
        if(x==1||x==3)//如果今天可以编程
            f[i][1]=min(f[i-1][0],f[i-1][2]);//昨天可以休息和健身
        if(x==2||x==3)//如果今天可以健身
            f[i][2]=min(f[i-1][0],f[i-1][1]);//昨天可以休息和编程
    }
	
	//输出
	//第n天我们可以有三种情况，输出其中的最小值
    cout<<min(f[n][0],min(f[n][1],f[n][2]))<<endl;
    system("pause");
    return 0;
}

写在最后

如果代码有任何问题，欢迎评论或者私信斧正。如果内容对对你有启发，不妨点个赞吧