题解 P3609 【[USACO17JAN]Hoof, Paper, Scissor蹄子剪刀…】
MorsLin
2019-01-07 16:50:28
这种$DP$能有蓝题？反正我是不信
---
#### 状态
``f[i][j][k]`` 表示当前是第$i$局，已经变了$j$次手势，当前的手势是$k$，之后能赢多少场
#### 转移
用一种类似后缀和的方式，记录下如果当前变为该手势，则之后能赢多少局（其实这步并不必要，但我觉得更好理解一些）
之后疯狂判断就好了
``f[i][j][k]=max(f[i][j][k],f[i][j-1][k]-sum_now[i]+sum_change[i])``
其中``sum_now[i]``为 当前手势之后能赢多少场，``sum_change[i]``为 改变后的手势之后能赢多少场
#### $code$
特判有点冗杂，但还是挺容易理解的……
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define gc() getchar()
using namespace std;
LL read(){LL k=0,f=1;char c=gc();while(c<'0'||c>'9'){if(c=='-') f=-1; c=gc();}while(c>='0'&&c<='9')k=k*10+c-48,c=gc();return k*f;}
char read_c(){char c=gc();while((c<'a'||c>'b')&&(c<'A'||c>'Z'))c=gc();while((c>='a'&&c<='z')||(c>='A'&&c<='Z'))return c;}
int f[100010][21][4],s[100010],m[100010],b[100010];
int ans;
int main(){
int n=read(),k=read();
for(int i=n;i>=1;i--){
char c=read_c();
s[i]=s[i+1]; m[i]=m[i+1]; b[i]=b[i+1];
if(c=='P') s[i]++;
if(c=='S') m[i]++;
if(c=='H') b[i]++;
}
f[0][0][1]=s[1]; f[0][0][2]=m[1]; f[0][0][3]=b[1];
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
f[i][j][1]=f[i-1][j][1]; f[i][j][2]=f[i-1][j][2]; f[i][j][3]=f[i-1][j][3];
ans=max(ans,max(f[i][j][1],max(f[i][j][2],f[i][j][3])));
if(j==0) continue;
f[i][j][1]=max(f[i][j][1],max(f[i][j-1][2]-m[i]+s[i],f[i][j-1][3]-b[i]+s[i]));
f[i][j][2]=max(f[i][j][2],max(f[i][j-1][1]-s[i]+m[i],f[i][j-1][3]-b[i]+m[i]));
f[i][j][3]=max(f[i][j][3],max(f[i][j-1][1]-s[i]+b[i],f[i][j-1][2]-m[i]+b[i]));
ans=max(ans,max(f[i][j][1],max(f[i][j][2],f[i][j][3])));
}
}
cout<<ans;
return 0;
}
```