1 条题解

  • 2
    @ 2025-12-12 13:19:23

    DP

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=2e5+10;
    int f[4][N];char s[N];
    signed main()
    {
    	int n;scanf("%lld%s",&n,s+1);
    	memset(f,0,sizeof f);
    	for(int i=1;i<=n;i++)
    	{
    		if(s[i]=='R')
    		{
    			f[1][i]=max(f[2][i-1],f[3][i-1]);
    			f[2][i]=max(f[1][i-1]+1,f[3][i-1]+1);
    		}
    		else if(s[i]=='P')
    		{
    			f[2][i]=max(f[1][i-1],f[3][i-1]);
    			f[3][i]=max(f[1][i-1]+1,f[2][i-1]+1);
    		}
    		else
    		{
    			f[3][i]=max(f[1][i-1],f[2][i-1]);
    			f[1][i]=max(f[2][i-1]+1,f[3][i-1]+1);
    		}
    	}
    	printf("%lld\n",max(max(f[1][n],f[2][n]),f[3][n]));
    	return 0;
    }
    
    • 1

    信息

    ID
    8000
    时间
    2000ms
    内存
    1024MiB
    难度
    8
    标签
    递交数
    31
    已通过
    6
    上传者