admin 管理员组

文章数量: 1184232

luogu P3609 [USACO17JAN]Hoof, Paper, Scissor蹄子剪刀…

算法：记忆化搜索

难度：NOIP

题解：暴力枚举所有情况，更新dp数组的值，记忆化搜索即可

代码如下：

时间复杂度：常数

玄学油画：

1、手写max函数

2、i++改成i++

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#define ll long long 
#define N 100005
using namespace std;
char str[5];
int f[N];
int ans,n,k;
int dp[N][25][5];
int max(int x,int y)
{return x>y?x:y;
} 
int dfs(int typ,int chan,int po)
{if(po>n||chan>k) return 0;if(dp[po][chan][typ]) return dp[po][chan][typ];//记忆化 if(chan==k){if(typ==1&&f[po]==3) dp[po][chan][typ]=dfs(typ,chan,po+1)+1;if(typ==2&&f[po]==1) dp[po][chan][typ]=dfs(typ,chan,po+1)+1;if(typ==3&&f[po]==2) dp[po][chan][typ]=dfs(typ,chan,po+1)+1;if(typ==1&&f[po]!=3) dp[po][chan][typ]=dfs(typ,chan,po+1);if(typ==2&&f[po]!=1) dp[po][chan][typ]=dfs(typ,chan,po+1);if(typ==3&&f[po]!=2) dp[po][chan][typ]=dfs(typ,chan,po+1);}else{if(typ==1&&f[po]==3) dp[po][chan][typ]=max(dfs(typ,chan,po+1)+1,max(dfs(3,chan+1,po+1)+1,dfs(2,chan+1,po+1)+1));if(typ==2&&f[po]==1) dp[po][chan][typ]=max(dfs(typ,chan,po+1)+1,max(dfs(3,chan+1,po+1)+1,dfs(1,chan+1,po+1)+1));if(typ==3&&f[po]==2) dp[po][chan][typ]=max(dfs(typ,chan,po+1)+1,max(dfs(1,chan+1,po+1)+1,dfs(2,chan+1,po+1)+1));if(typ==1&&f[po]!=3) dp[po][chan][typ]=max(dfs(typ,chan,po+1),max(dfs(3,chan+1,po+1),dfs(2,chan+1,po+1)));if(typ==2&&f[po]!=1) dp[po][chan][typ]=max(dfs(typ,chan,po+1),max(dfs(3,chan+1,po+1),dfs(1,chan+1,po+1)));if(typ==3&&f[po]!=2) dp[po][chan][typ]=max(dfs(typ,chan,po+1),max(dfs(1,chan+1,po+1),dfs(2,chan+1,po+1)));}return dp[po][chan][typ];
}
int main()
{scanf("%d%d",&n,&k);for(int i = 1;i <= n;++i/*玄学++i优化*/)   //或者手写max！ {scanf("%s",str+1);if(str[1]=='H') f[i]=1;//石头else if(str[1]=='P') f[i]=2;//布else if(str[1]=='S') f[i]=3;//剪刀 }ans=max(dfs(1,0,1),max(dfs(2,0,1),dfs(3,0,1)));printf("%d\n",ans);return 0 ;
}

 

本文标签： Luogu P3609 USACO17JANHoof Paper Scissor蹄子剪刀…

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