admin 管理员组

文章数量: 1184232

洛谷P3609 [USACO17JAN]Hoof, Paper, Scissor蹄子剪刀

DP大法好

dp思路

定义 f [ i ] [ j ] [ 1 / 2 / 3 ] f[i][j][1/2/3] f[i][j][1/2/3]表示dp到第i位，变了j次，当前是石头/剪刀/布的最大胜出局数，转移的话就在 m a x ( f [ i − 1 ] [ j ] [ k ] , f [ i − 1 ] [ j − 1 ] [ e ! = k ] ) max (f[i-1][j][k] , f[i-1][j-1][e!=k]) max(f[i−1][j][k],f[i−1][j−1][e!=k])因为e有两种取值，所以一共是九种转移，取max，最后在三种手势里取max就行了

代码

//By AcerMo
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=100500;
int n,m;
char a[M];
int f[M][21][4],b[M];
inline int win(int x,int y)
{if (x==1&&y==2) return 1;if (x==2&&y==3) return 1;if (x==3&&y==1) return 1;return 0;
}
signed main()
{cin>>n>>m;for (int i=1;i<=n;i++) getchar(),a[i]=getchar();for (int i=1;i<=n;i++)b[i]=a[i]=='H'?1:(a[i]=='S'?2:3);for (int i=1;i<=n;i++)for (int k=1;k<=3;k++)f[i][0][k]=f[i-1][0][k]+win(k,b[i]);for (int i=1;i<=m;i++)for (int k=1;k<=n;k++){f[k][i][1]=max(f[k-1][i][1],max(f[k-1][i-1][2],f[k-1][i-1][3]))+win(1,b[k]);f[k][i][2]=max(f[k-1][i][2],max(f[k-1][i-1][1],f[k-1][i-1][3]))+win(2,b[k]);f[k][i][3]=max(f[k-1][i][3],max(f[k-1][i-1][1],f[k-1][i-1][2]))+win(3,b[k]);}int ans=0;ans=max(f[n][m][1],max(f[n][m][2],f[n][m][3]));cout<<ans;return 0;
}

本文标签： 洛谷P3609 USACO17JANHoof Paper Scissor蹄子剪刀

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