codeforces 698A（暴力）
题意描述
Vasya has n days of vacations! So he decided to improve his IT skills and do sport. Vasya knows the following information about each of this n days: whether that gym opened and whether a contest was carried out in the Internet on that day. For the i-th day there are four options:
on this day the gym is closed and the contest is not carried out; on this day the gym is closed and the contest is carried out; on this day the gym is open and the contest is not carried out; on this day the gym is open and the contest is carried out. On each of days Vasya can either have a rest or write the contest (if it is carried out on this day), or do sport (if the gym is open on this day).
Find the minimum number of days on which Vasya will have a rest (it means, he will not do sport and write the contest at the same time). The only limitation that Vasya has — he does not want to do the same activity on two consecutive days: it means, he will not do sport on two consecutive days, and write the contest on two consecutive days.
给你n个数字，为0的时候表示可以休息，为1的时候表示比赛，为2的时候表示可以健身，为3的时候比赛和健身都可以。不能连续两天比赛或者健身，求能够休息的最少天数
思路
这道题的tag是dp，但被我一顿瞎搞搞过了。需要注意的地方就是为3的时候，如果连续出现了奇数个3，那么第一个3应该是与下一个不为3的相反。例如3 3 3 1，此时的序列应该为2 1 2 1.如果连续出现了偶数个3，那么第一个3应该是与下一个不为3的相同。例如3 3 3 3 1，此时的序列应该为1 2 1 2 1。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=1005;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;
int a[N];
bool st[2];
void solve(){
int n;cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int ans=0;
for(int i=0;i<n;i++){
if(a[i]==0) ans++,st[0]=false,st[1]=false;
if(a[i]==1 && st[0]) ans++,st[0]=false;
else if(a[i]==1 && !st[0]) st[0]=true,st[1]=false;
if(a[i]==2 && st[1]) ans++,st[1]=false;
else if(a[i]==2 && !st[1]) st[1]=true,st[0]=false;
if(a[i]==3){
if(st[0]) st[1]=true,st[0]=false;
else if(st[1]) st[0]=true,st[1]=false;
else if(!st[0] && !st[1]){
int j=i;
while(j<n && a[j]==3) j++;
if((j-i)&1){
if(a[j]==1 || a[j]==0) st[1]=true;
if(a[j]==2) st[0]=true;
}else{
if(a[j]==1 || a[j]==0) st[0]=true;
if(a[j]==2) st[1]=true;
}
}
}
}
cout<<ans<<endl;
}
int main(){
IOS;
solve();
return 0;
}腾讯云开发者
