题目大意：给你n天 0表示今天只能休息 1表示今天可以休息或者健身 2表示今天可以休息或者做题 3表示今天可以休息或者做题或者健身 但两天不能连续健身 不能连续做题的情况下 问你最少休息几天？
解题思路：这道题有两种做法，一种是贪心，一种是动态规划 。万物皆动态规划也不是嘘的。 首先我先说下贪心： 开个cnt来记录休息的天数 因为是贪心 要贪最好不休息 先判断第一天 然后从第二天开始遍历 如果是0就必须休息 这个没得说 如果是1就判断它上一个是不是1 这里1表示状态健身 如果是++ 并把这个数标记为0 0表示状态休息嘛 可以理解为更新 当遇到2时像上面一样判断就可以了 用贪心并没有什么难度、、、
下面我就上代码了。。。
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <map> #include <cmath> #include <queue> #include <string> #include <vector> #include <set> using namespace std; #define sc(x) scanf("%d",&x) #define dsc(x,y,z) scanf("%d %d %d",&x,&y,&z) #define pr(x) printf("%d\n",x) #define FOR(i,n,o) for(int i=o;i<=n;i++) #define lcr(a,b) memset(a,b,sizeof(a)) #define maxn 105 int n,cnt; int a[maxn]; int main() { while(~sc(n)) { cnt=0; FOR(i,n,1) { sc(a[i]); } if(a[1]==0) cnt++; FOR(i,n,2) { if(a[i]==0) cnt++; if(a[i]==1) { if(a[i-1]==1) { cnt++; a[i]=0; } } if(a[i]==2) { if(a[i-1]==2) { cnt++; a[i]=0; } } if(a[i]==3) { if(a[i-1]==1) a[i]=2; if(a[i-1]==2) a[i]=1; } } pr(cnt); } return 0; }接下来 我们来解释下动态规划怎么来做这道题吧 首先要想怎么用动态规划来A掉此题 此题的状态无非就3种 休息 健身 做题，我们可以用dp[i][j]来做，dp[i][j]代表第i天做j个事情最少休息的天数
第二步我们就要来找动态转移方程
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][2],dp[i-1][0]); dp[i][2]=min(dp[i-1][1],dp[i-1][0]); 这三个动态转移方程 仔细观察还是能够发现的
有了这个 动态就很好写了
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <map> #include <cmath> #include <queue> #include <string> #include <vector> #include <set> using namespace std; #define sc(x) scanf("%d",&x) #define dsc(x,y,z) scanf("%d %d %d",&x,&y,&z) #define pr(x) printf("%d\n",x) #define FOR(i,n,o) for(int i=o;i<=n;i++) #define lcr(a,b) memset(a,b,sizeof(a)) #define ll long long #define maxn 105 #define INF 0x3f3f3f int n,dp[maxn][5]; int a[maxn]; int main() { while(~sc(n)) { lcr(dp,INF);//初始化大点的数 dp[0][0]=0; int m; FOR(i,n,1) { sc(m); dp[i][0]=min(dp[i-1][0],min(dp[i-1][1],dp[i-1][2]))+1; if(m==1) dp[i][m]=min(dp[i-1][2],dp[i-1][0]); if(m==2) dp[i][m]=min(dp[i-1][1],dp[i-1][0]); if(m==3) { dp[i][1]=min(dp[i-1][2],dp[i-1][0]); dp[i][2]=min(dp[i-1][1],dp[i-1][0]); } } int cnt=INF;//初始化大数 for(int i=0;i<=2;i++) cnt=min(dp[n][i],cnt); pr(cnt); } return 0; }END！！！！！！！！！！！！！！！！！
