【题解】CF698A

【题解】CF698A

题目翻译

题目分析

一道dp题

一开始想把dp[i]定义为到第i天可以最少休息几天，结果发现写不出状态转换方程；

考虑到第i天和第i-1天之间是有关系的，所以把数组改为dp[i][j]，i是天数，j是第i天的状态（1，2，3代表休息，比赛，健身）然后对每一天分类讨论即可

还有一个小细节：注意到选择第i天的时候应该是选择最小的一个答案，然而很显然并不是所有状态都是可以选择的，所以在选择答案ans=min(dp[n][1],dp[n][2],dp[n][3])的时候，有一些状态可能是0，因此，在初始化数组的时候应该将数组初始化为一个很大的数，避免了这个bug

完整代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;int dp[1050][4];//1休息 2锻炼 3比赛
int a[1050];int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];memset(dp,127,sizeof(dp));dp[0][1]=0;dp[0][2]=0;dp[0][3]=0;for(int i=1;i<=n;i++){if(a[i]==0){dp[i][1]=min(dp[i-1][1],min(dp[i-1][2],dp[i-1][3]))+1;}else if(a[i]==1){dp[i][1]=min(dp[i-1][1],min(dp[i-1][2],dp[i-1][3]))+1;dp[i][3]=min(dp[i-1][1],dp[i-1][2]);}	else if(a[i]==2){dp[i][1]=min(dp[i-1][1],min(dp[i-1][2],dp[i-1][3]))+1;dp[i][2]=min(dp[i-1][1],dp[i-1][3]);}else {dp[i][1]=min(dp[i-1][1],min(dp[i-1][2],dp[i-1][3]))+1;dp[i][2]=min(dp[i-1][1],dp[i-1][3]);dp[i][3]=min(dp[i-1][1],dp[i-1][2]);}}int ans=min(dp[n][1],min(dp[n][2],dp[n][3]));cout<<ans<<endl;return 0;
}