文章图片
文章图片
开始做的时候怎么想也想不出来，知道是动态规划，但是就是想不出来，应该是题目做少了...
然后参考了一篇文章：
(刷题笔记) 牛客网 腾讯2020校园招聘-后台 3.逆序对_Lucky&Happy的博客-CSDN博客
已经讲的很明白了，这里说一下他的基本思想：
设置一个dp[3][n]的数组来动态规划，各个维度的含义如下：
1.dp[0][i]表示第i天休息的时候最少休息天数，容易想到dp[0][i]=min(dp[0][i-1],dp[1][i-1],dp[2][i-1])+1
2.dp[1][i]表示第i天工作时的最小休息天数，当然这里的判断条件首先是当天可以工作，那dp[1][i]的值是什么呢？也容易想到，由于不会连续两天工作或锻炼，所以dp[1][i]=min(dp[0][i-1],dp[2][i-1])，当然，也有可能直接是dp[1][i]=dp[0][i-1]，这是当前一天不能锻炼的时候。当然，以上情况是基于当天是可以工作的，如果不能工作就直接dp[1][i]=n，这样也不会影响到之后的情况
3.dp[2][i]的求法和2是对称的
【牛客网|牛客网（2020腾讯后台4：假期）】之后要注意初始化的问题，dp[0][0]=1，当天选择休息，之后如果是可以工作，那么dp[1][0]=0，锻炼也一样。
代码如下所示：
#include
usingnamespace std;
int main() {
int n;
cin>>n;
vector work(n);
vector exercise(n);
for (int i = 0;
i < n;
++i) {
cin>>work[i];
}
for (int i = 0;
i < n;
++i) {
cin>>exercise[i];
}
//dp[0][i]表示第i天休息的最少休息天数
//dp[1][i]表示第i天工作的最少的休息天数
//dp[2][i]表示第i天锻炼的最少的休息天数
vector> dp(3, vector(n,0));
//边界条件
dp[0][0]=1;
if (work[0]) dp[1][0]=0;
if (exercise[0]) dp[2][0]=0;
for (int i = 1;
i < n;
++i) {
//该天公司营业
if (work[i]){
//前一天可以锻炼
if (exercise[i-1]){
dp[1][i]=min(dp[0][i-1],dp[2][i-1]);
}else{
dp[1][i]= dp[0][i-1];
}
}else{
dp[1][i]=n;
}
//该天可以锻炼
if (exercise[i]){
if (work[i-1]){
dp[2][i]=min(dp[0][i-1],dp[1][i-1]);
}else{
dp[2][i]=dp[0][i-1];
}
}else{
dp[2][i]=n;
}
dp[0][i]=min(min(dp[0][i-1],dp[1][i-1]),dp[2][i-1])+1;
}
cout< 推荐阅读
- C++短暂之旅|4. C++运算符
- 学在信息——牛刀小试
- 信息论与编码|学在信息——渐露锋芒
- Chrome中Cookie提取工具教程
- 大唐杯学习|大唐杯5G考前冲刺篇（回顾全文重点必看）
- 分治法与动态规划的区别
- 动态规划算法介绍
- MySQL|MySQL进阶之存储引擎【InnoDB、MySAM、Memory】
- #HTML|javascript------＞对象数据类型