「Test」游戏

题意：你和小 $B$ 准备玩 $N(N\le 100000)$ 回合的石头剪刀布，你已经预测出小 $B$ 未来 $N$ 回合的手势，但你只愿意在过程中改变 $K(K\le 20)$ 次手势(最开始手势任意)，请问你最多能赢多少场。

一道线性 DP。

我们设 $f _{i,j,k}$ 表示前 $i$ 次改变了 $j$ 次手势，第 $i$ 局手势为 $k$ 能赢的最多局数($k=0$ 为石头，$k=1$ 为剪刀，$k=2$ 为布)。

初始化把 $f$ 设为极小值， $f_ {0,0,k}(0\le k\le 2)=0,f_ {i,0,j}=f_ {i-1,0,j}+\text{compete}(j,num _{i})$，其中 $\text{compete}$ 为判断这局是否赢得函数，$num _{i}$ 为第 $i$ 局小 $B$ 的手势。

然后就可以开始递推了，分别处理 $f_ {i,j,k}(0\le k\le 2)$ 的三种情况，三种情况类似，这里只举出 $f _{i,j,0}$ 的转移方程：

$$f_ {i,j,0}=\max(f _{i,j,0},f _{i-1,j,0}+\text{compete}(0,num _{i}),f_ {i-1,j-1,1}+\text{compete}(0,num _{i}),f_ {i-1,j-1,2}+\text{compete}(0,num _{i}))$$

最后答案即为 $\max(f _{n,k,0},f _{n,k,1},f _{n,k,2})$。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 1e9;
using namespace std;
const int maxn=100011,maxk=21;
int n,k,f[maxn][maxk][3],num[maxn];//0石头1剪刀2布
char c;
int compete(int a,int b)
{
	if(a==0&&b==1)
		return 1;
	else if(a==1&&b==2)
		return 1;
	else if(a==2&&b==0)
		return 1;
	else
		return 0;
}
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("\n%c",&c);
		if(c=='H')
			num[i]=0;
		else if(c=='S')
			num[i]=1;
		else
			num[i]=2;
	}
	memset(f,-0x3f,sizeof(f));
	f[0][0][0]=f[0][0][1]=f[0][0][2]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=2;j++)
			f[i][0][j]=f[i-1][0][j]+compete(j,num[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++)
		{
			int x=compete(0,num[i]);
			int y=compete(1,num[i]);
			int z=compete(2,num[i]);
			f[i][j][0]=max(max(f[i][j][0],f[i-1][j][0]+x),max(f[i-1][j-1][1]+x,f[i-1][j-1][2]+x));
			f[i][j][1]=max(max(f[i][j][1],f[i-1][j][1]+y),max(f[i-1][j-1][0]+y,f[i-1][j-1][2]+y));
			f[i][j][2]=max(max(f[i][j][2],f[i-1][j][2]+z),max(f[i-1][j-1][0]+z,f[i-1][j-1][1]+z));
			/*for(int p=0;p<=2;p++)
				printf("%d %d %d %d\n",i,j,p,f[i][j][p]);*/
		}
	printf("%d",max(max(f[n][k][0],f[n][k][1]),f[n][k][2]));
	return 0;
}