admin 管理员组

文章数量: 1184232

【洛谷P3609】Hoof,Paper,Scissor G【DP】


L u o g u l i n k Luogu~link Luogu link

分析：

d p dp dp 设 f i , j , 0 , 1 , 2 f_{i,j,0,1,2} fi,j,0,1,2​表示前 i i i轮变换 j j j次手势 最后出 0 / 1 / 2 0/1/2 0/1/2 最多能赢轮数 0 0 0代表 H H H 1 1 1代表 S S S 2 2 2代表 P P P
转移显然

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

只需要预处理 H i , S i , P i H_i,S_i,P_i Hi​,Si​,Pi​即可

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,k,f[N][25][3],P[N],H[N],S[N],ans;
int main(){ scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){char op;cin>>op;if(op=='P') P[i]++;if(op=='H') H[i]++;if(op=='S') S[i]++;}f[1][0][0]=H[1];f[1][0][1]=S[1];f[1][0][2]=P[1];for(int i=1;i<=n;i++)for(int j=0;j<=k;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])));}for(int i=0;i<=k;i++)ans=max(ans,max(f[n][i][0],max(f[n][i][1],f[n][i][2])));printf("%d",ans);return 0;
}

本文标签： 洛谷P3609Hoof Paper Scissor GDP

版权声明：本文标题：【洛谷P3609】Hoof,Paper,Scissor G【DP】 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1699066718a326037.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。