动态规划求调
查看原帖
动态规划求调
712296
Alex_smy楼主2024/8/8 14:16
#include <bits/stdc++.h>
using namespace std;
int n,dp[5][200005];
char c;
int main(){
	scanf("%d",&n);
	scanf("%c",&c);
	if(c=='R') dp[3][1]=1;
	else if(c=='P') dp[1][1]=1;
	else dp[2][1]=1;
	for(int i=2;i<=n;i++){
		scanf("%c",&c);
		if(c=='R'){
			dp[1][i]=max(dp[2][i-1],dp[3][i-1]);
			dp[2][i]=max(dp[1][i-1],dp[3][i-1])+1;
		}
		else if(c=='P'){
			dp[2][i]=max(dp[1][i-1],dp[3][i-1]);
			dp[3][i]=max(dp[1][i-1],dp[2][i-1])+1;
		}
		else{
			dp[3][i]=max(dp[1][i-1],dp[2][i-1]);
			dp[1][i]=max(dp[2][i-1],dp[3][i-1])+1;
		}
	}
	printf("%d",max({dp[1][n],dp[2][n],dp[3][n]}));
	return 0;
}
2024/8/8 14:16
加载中...