题解 P3609 【[USACO17JAN]Hoof, Paper, Scissor G】
zgf519orz
·
·
题解
一眼看上去，像是经典的一大类 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）
```cpp
#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$ 的巧妙之处。
废话不多说，献上蒟蒻的代码：
```cpp
#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