【C++编程题】疫情期间（动态规划，递归）
【问题描述】
正值新冠疫情期间，阿迪没法返回学校学习，他希望通过参加⼀些⽐赛来提⾼⼀下编程技能，同时做做运动。他收集了接下来的 n 天⾥每⼀天的信息，包括健⾝房是否开放，或者互联⽹上是否有程序设计竞赛。
第 i 天可以有以下四种情况之⼀：
该天健⾝房不开放，互联⽹上也没有竞赛
该天健⾝房不开放，但互联⽹上有竞赛
该天健⾝房开放，但互联⽹上没有竞赛
该天健⾝房开放，互联⽹上也有竞赛
每天阿迪要么休息，要么编写程序（如果该天有竞赛），要么做运动（如果该天健⾝房开放）。
现在有⼀个限制条件：不能连续两天都去做运动，或者连续两天都编写程序。阿迪对⾃⼰要求很⾼，希
望尽量多写程序或者多做运动，使得休息的天数尽量最少，求出这个天数。
【输⼊形式】
输⼊的第⼀⾏为⼀个正整数 n (1≤ n ≤ 100)，表⽰接下来的天数。
第⼆⾏为⼀个⽤空格分隔的整数序列 a1、a2、…、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
【样例输出1】
2
【样例输⼊2】
7
1 3 3
2 1 2 3
【样例输出2】
【样例输⼊3】
2
2 2
【样例输出3】
1
【样例说明】
在第⼀个样例中，阿迪在第⼀天编写程序，在第三天做运动，因此他仅有两天可以休息。
在第⼆个样例中，阿迪可以在第1、3、5、7天编写程序，其他天做运动，因此没有哪天休息。
在第三个样例中，阿迪可以在第1天或第2天做运动，但不能连续两天运动，因此他有⼀天休息。
【思路】
这道题⼀开始⽤了递归，发现超时...
然后天真地⽤了⼀维数组作为dp...离谱了...搞了很久才发现⾃⼰搞错了
跟着别⼈的代码敲了⼀遍，果然很巧妙...
dp[i][j] 表⽰第i天做了活动j所得到的最⼩休息天数
0休息，1编程，2健⾝, 先全部初始化为很⼤的天数 @
0（1）0（1）0（1）0（2）0（）0（）
1（@）1（0）1（@）1（@）1（）1（）
2（0）2（@）2（@）2（1）2（）2
210220
第⼀天为2，可以休息，那么dp[1][0]=1; 也可以选择健⾝，因此dp[1][2]=0
第⼆天为1，可以休息，前⼀天中最⼩为0，因此dp[2][0] = 0+1 =1;
编程递归函数
也可以选择编程，同样的，前⼀天中健⾝和休息中，最⼩为0，dp[2][1]=0;
第三天为0，只能休息，前⼀天中最⼩为0，因此dp[3][0] = 0 +1 =1;
第四天为1，可以休息，前⼀天中最⼩为1，dp[4][0] = 1 + 1 =2 ；
也可以健⾝，前⼀天中，休息和编程中最⼩值为1，因此dp[4][2]=1 ;
......
最后⼀天⾥，三个中最⼩的就是了
【AC代码】
#include<string>
#include<iostream>
#include<sstream>
#include<stack>
#include<cmath>
using namespace std;
/*
单纯递归会超时要⽤动态规划~ 保存已经算好的数据
后⼀天的情况会跟前⼀天情况相关联！
*/
int a[110];
int n;
int dp[110][3];  //0休息，1编程，2健⾝    i表⽰时间（从1开始）,j表⽰这天⼲啥 ,
//dp[i][j]表⽰i天做j事情所得到的休息天数
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];  //下标从1开始，第⼀天
for(int i;i<=n;i++)
for(int j=0;j<3;j++)
dp[i][j]=10000;  //初始化⼀个⼤数字，为的是后⾯选取最⼩休息天⽅便
//动态规划要有初始值
if(a[1]==1) dp[1][1]=0;  //第⼀天编程，第⼀天休息0天
if(a[1]==2) dp[1][2]=0;  //第⼀天健⾝，第⼀天休息0天
if(a[1]==3) {
dp[1][1]=0;
dp[1][2]=0;
}
//今天做或者不做某件事⼉，dp[1][j]中会有⼀个或两个改变，其它仍是10000极⼤值
dp[1][0]=1;  //第⼀天如果休息，则休息天数+1
for(int i=2;i<=n;i++){    //从第⼆天开始
if(a[i]==1){            //今天想编程的话，前⼀天只能是健⾝或者休息，最⼩休息天数不变    dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
}else if(a[i]==2){      //今天想健⾝的话，前⼀天只能是编程或者休息，最⼩休息天数不变    dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
}else if(a[i]==3){
dp[i][1]=min(dp[i-1][0],dp[i-1][2]);
dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
}
dp[i][0]= 1 + min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]));  //如果今天选择休息，那么天数+1  }
//在最后⼀天中，出最⼩休息天数
cout<<min(dp[n][0],min(dp[n][1],dp[n][2]))<<'\n';
}
【写在后⾯】
觉得对你有帮助的话记得⼀键三连哦~（误
相关题⽬放在了【HNU CJ】专栏
如果有啥问题可以评论留⾔或者私我哦~

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。