# MorsLin 的博客

### 题解 P3609 【[USACO17JAN]Hoof, Paper, Scissor蹄子剪刀…】

posted on 2019-01-07 16:50:28 | under 题解 |

#### 状态

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])

#### $code$

#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;}
int f[100010][21][4],s[100010],m[100010],b[100010];
int ans;
int main(){
for(int i=n;i>=1;i--){
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;
}