你可能听说过“石头，剪刀，布”的游戏。FJ的牛喜欢玩一个类似的游戏，它们称之为“蹄子，剪刀，布”（“蹄子”就是“石头”）。
游戏规则很简单：比赛双方同时数到3，然后同时出一个手势，代表“蹄子”“剪刀”或“布”。“蹄子”胜“剪刀”，“剪刀”胜“布”，“布”胜“蹄子”。举个例子，第一头牛出“蹄子”，第二头牛出“布”，则第二头牛胜利。当然，也可以“平局”（如果两头牛手势相同的话）。
FJ想对阵自己获奖的牛，贝西。贝西作为一个专家，能够预测FJ的手势。不幸的是，贝西作为一头牛，也十分的懒惰。事实上，她只愿意变换固定次数的手势来完成游戏。例如，她可能只想变1次，则他可能出“蹄子”几次，剩下的都出“布”。
鉴于贝西预测FJ会出的手势，以及她想变的次数，求出她最多能赢多少场
5 1 P P H P S
4 数位dp写不动来水记搜。
#include<bits/stdc++.h> using namespace std; const int Maxn=100005; int n,k,a[Maxn],f[Maxn][25][5]; bool check(int a,int b){ if(a==0&&b==2)return 1; if(a==1&&b==0)return 1; if(a==2&&b==1)return 1; return 0; } int DFS(int x,int l,int z){ if(l==-1)return 0; if(x==1)return check(z,a[x]); if(~f[x][l][z])return f[x][l][z]; int ret=0; for(int i=0;i<3;++i){ ret=max(ret,DFS(x-1,l-(i!=z),i)+(l-(i!=z)>=0?check(i,a[x]):0));//注意这里能不能check } return f[x][l][z]=ret; } int main(){ cin>>n>>k; for(int i=1;i<=n;++i){ char c=getchar();while(!isalpha(c))c=getchar(); if(c=='H')a[i]=0;//石头 if(c=='P')a[i]=1;//布 if(c=='S')a[i]=2;//剪刀 } memset(f,-1,sizeof(f)); cout<<max(DFS(n,k,0),max(DFS(n,k,1),DFS(n,k,2)))<<endl; return 0; }
