大佬 求助
查看原帖
大佬 求助
867904
xinlong666楼主2023/12/3 11:06
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000010];
int dp[1000010][4];
int main(){
	cin >> n;
	for (int i = 1 ; i <= 1000000 ; i ++){
		dp[i][0] = dp[i][1] = dp[i][2] = 1e9;
	}
	for (int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		a[i]++;
	}
	dp[1][a[1]]=0;
	//cout << dp[1][0] << ' '<< dp[1][1] << ' '<< dp[1][2] << ' ' << endl;
	for (int i = 2 ; i <= n ; i ++){
		if(dp[i-1][0] != 1e9){
			dp[i][a[i]] = min(dp[i][a[i]],dp[i-1][0]);
			if(a[i] == 0){
				dp[i][0] = min(dp[i][0],dp[i-1][0]);
			}else if(a[i] == 1){
				dp[i][0] = min(dp[i][0],dp[i-1][0]+1);
			}else{
				dp[i][1] = min(dp[i][0],dp[i-1][0]+1);
				dp[i][0] = min(dp[i][0],dp[i-1][0]+2);
			}
		}
		if(dp[i-1][1] != 1e9){
			if(a[i] != 0){
				dp[i][a[i]] = min(dp[i][a[i]],dp[i-1][1]);
			}
		}
		if(dp[i-1][2] != 1e9){
			if(a[i] == 2){
				dp[i][a[i]] = min(dp[i][a[i]],dp[i-1][2]);
			}
		}
		//cout << dp[i][0] << ' '<< dp[i][1] << ' '<< dp[i][2] << ' ' << endl;
	}
	int ans = 1e9;
	for (int i = 0 ; i <= 2 ; i ++){
		ans = min(dp[n][i],ans);
	}
	if(ans == 1e9){
		cout << "BRAK";
	}else{
		cout << ans;
	}
	return 0;
} 
2023/12/3 11:06
加载中...