admin 管理员组

文章数量: 1184232

P3609 [USACO17JAN]Hoof, Paper, Scissor

传送门（洛谷）

记忆化搜索形式的动归
状态：
f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]表示当前是第 i i i轮，用了 j j j次换的机会且当前出的是 k , 1 < = k < = 3 。 k k,1<=k<=3。k k,1<=k<=3。k是剪刀石头布

分为变还是不变两种状态，搜就行了

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);i++)
#define don(i,a,b) for(register int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int maxn=2e5+10;
const int maxm=1e3+10;
char s[maxn];
int n,m;
int a[maxn],point[4][4],f[maxn][30][4];template <class t> inline void read(t &x)
{int f=1;x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)){x=10*x+ch-'0';ch=getchar();}x*=f;
}void readdata() {read(n);read(m);rep(i,1,n) {scanf("%s",&s[i]);if(s[i]=='P') a[i]=3;if(s[i]=='H') a[i]=2;if(s[i]=='S') a[i]=1;}
}inline int dfs(int x,int y,int now) {if(f[x][y][now]) return f[x][y][now];if(x>n) return 0;f[x][y][now]=dfs(x+1,y,now)+point[now][a[x]];//如果不变得到的分数在加上当前得到的分数，是相同子问题if(y+1<=m) {rep(i,1,3) {if(now==i) continue;f[x][y][now]=max(f[x][y][now],dfs(x+1,y+1,i)+point[now][a[x]]);//如果变}}return f[x][y][now];
}void work() {memset(f,false,sizeof(f));point[1][2]=0;point[1][3]=1,point[1][1]=0;point[2][1]=1;point[2][3]=0,point[2][2]=0;point[3][1]=0;point[3][2]=1,point[3][3]=0;int ans=0;for(int i=0;i<=m; i++) {for(int j=1; j<=3; j++)ans=max(ans,dfs(1,i,j));}printf("%d\n",ans);
}int main() {freopen("input.txt","r",stdin);readdata();work();return 0;
}

本文标签： P3609 USACO17JANHoof Paper Scissor

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