自动搬运

查看原文

来自洛谷，原作者为

	zgf519orz ？？？！！！……

搬运于2025-08-24 21:50:43，当前版本为作者最后更新于2020-03-18 22:43:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一眼看上去，像是经典的一大类 $dp$ 题，我们可以枚举 Bassie 最后一次变换手势是第几轮，不过这里，为了判断 Bassie 有没有赢，我们要加上一维来表示 Bassie 最后一次出的是什么手势（0 -> H ，1 -> S ， 2 -> P）。

状态即为： $f[i][j][flag]$ 表示前 $i$ 轮，严格变换了 $j$ 次手势，并且最后一次出的是 $flag$ 手势所赢的最多次数。

前面说了。要枚举 “最后一次变换手势是第几轮”，那么我们设为第 $k$ 轮，显然，第 $i$ 轮有三种情况，即出 0 或 1 或 2 手势，而每种情况又对应第 $k$ 轮不同的手势，这里注意，第 $i$ 轮与第 $k$ 轮手势不可以相同（否则不用变换）。

贴下状态转移方程：

//分三大类，第i轮分别出0 1 2
//每大类又分2小类，具体见下
f[i][j][0]=max(f[i][j][0],max(f[k][j-1][1],f[k][j-1][2])+h[i]-h[k]);
//第k轮可出1 2，但不可出0

f[i][j][1]=max(f[i][j][1],max(f[k][j-1][0],f[k][j-1][2])+s[i]-s[k]);
//第k轮可出0 2，但不可出1

f[i][j][2]=max(f[i][j][2],max(f[k][j-1][0],f[k][j-1][1])+p[i]-p[k]);
//第k轮可出0 1，但不可出2

（温馨提示：#define AC TLE）

$AC$ 代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
//H 0
//S 1
//P 2

int n,m; 
int h[100005],s[100005],p[100005];
//这里用三个前缀数组记录1~i轮分别出H S P可以赢的轮数
int f[100005][25][3];
//DP数组

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		char tmp;
		cin >> tmp;
		h[i]=h[i-1];
		s[i]=s[i-1];
		p[i]=p[i-1];
		if(tmp=='H'){
			p[i]++;
		}
		if(tmp=='S'){
			h[i]++;
		}
		if(tmp=='P'){
			s[i]++;
		}
	}
	for(int i=1;i<=n;i++){
		f[i][0][0]=h[i];
		f[i][0][1]=s[i];
		f[i][0][2]=p[i];
	}//初始化，显然只要不变化手势，赢得轮数就是p s h数组记录的
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=i-1;k>=j;k--){//枚举上次变换手势的轮数
            			//状态转移
				f[i][j][0]=max(f[i][j][0],max(f[k][j-1][1],f[k][j-1][2])+h[i]-h[k]);
				f[i][j][1]=max(f[i][j][1],max(f[k][j-1][0],f[k][j-1][2])+s[i]-s[k]);
				f[i][j][2]=max(f[i][j][2],max(f[k][j-1][0],f[k][j-1][1])+p[i]-p[k]);    		
			}
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++){
		ans=max(ans,max(f[n][i][0],max(f[n][i][1],f[n][i][2])));
	}//由于没有强求必须变换m次,应在所有答案中取最大值
	printf("%d",ans);
	return 0;
}

不过显然，这份代码肯定会超时的，因为 $1 \le N \le 10^5$ （别跟我说N方过百万，暴力碾标算…………真香）。

那么考虑优化吧，在原先代码的基础上，枚举 $i$ 和 $j$ 的循环是少不了的，那么我们可不可以省略枚举 $k$ 的循环呢？

事实上，我们不需要考虑过多情况，当前状态只与 $i-1$ 的状态有关 ，why？

在之前的代码里，我们要求 $i$ 轮和 $k$ 轮手势不可一样，而由 $i-1$ 转移，就不需要考虑这么多了。

我们分析一下：

当第 $i$ 轮选择出与 $i-1$ 轮不同的手势时，就是前 $i-1$ 轮变 $j-1$ 次赢的数量加上第 $i$ 次是否可以赢。

而第 $i$ 轮选择出与 $i-1$ 轮相同的手势时，是不用变换的，也就是说前 $i-1$ 轮要变换 $j$ 次手势，而前 $i-1$ 轮是怎么变换这 $j$ 次手势的？我们根本不用关心，因为答案已经算过了，这就是 $dp$ 的巧妙之处。

废话不多说，献上蒟蒻的代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

int n,m;
bool h[100005],s[100005],p[100005];
//这里的h s p数组和上面不一样，表示的是第 $i$ 轮出H/S/P能否赢。
//当然可以省略这三个数组，写个函数也是可以滴~
int f[100005][25][3];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		char tmp;
		cin >> tmp;
		if(tmp=='H'){
			p[i]=1;
		}
		if(tmp=='S'){
			h[i]=1;
		}
		if(tmp=='P'){
			s[i]=1;
		}
     		//字符读入还是cin稳（只是个人看法）
	}
	//H 0
	//S 1
	//P 2
	f[1][0][0]=h[1];
	f[1][0][1]=s[1];
	f[1][0][2]=p[1];
   	//初始化也简单了呢，只有1轮，变换0次，答案显然
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			f[i][j][0]=max(f[i][j][0],
            			   max(f[i-1][j][0]+h[i],
                           	   max(f[i-1][j-1][1]+h[i],f[i-1][j-1][2]+h[i])));
			f[i][j][1]=max(f[i][j][1],
            			   max(f[i-1][j][1]+s[i],
                           	   max(f[i-1][j-1][0]+s[i],f[i-1][j-1][2]+s[i])));
			f[i][j][2]=max(f[i][j][2],
            	  		   max(f[i-1][j][2]+p[i],
                           	   max(f[i-1][j-1][0]+p[i],f[i-1][j-1][1]+p[i])));
            		//可能max有点多，看得有些复杂，稍微解释一下吧。
                 	//只以f[i][j][0]为例，第i-1轮可以出0 1 2，出0时对应状态为f[i-1][j][0]。
                    	//出1时为f[i-1][j-1][1]+h[i]，出2时为f[i-1][j-1][2]+h[i]
                        //f[i][j][1/2]也差不多，只要把其中最后一维的数改一下，再把h[i]改为p/s[i]就可以喽
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++){
		ans=max(ans,max(f[n][i][0],max(f[n][i][1],f[n][i][2])));
	}//同样枚举变换次数选择最优解
	printf("%d",ans);
	return 0;
    	//华丽结束~~~
}

呼，写得真累，最后再 恬不知耻 地请大家点个赞吧 $QwQ$