【动态规划】P3609 [USACO17JAN] Hoof, Paper, Scissor G-北京尧图网络

本文涉及知识点C动态规划P3609 [USACO17JAN] Hoof, Paper, Scissor G题目背景本题与银组同名题目在题意上一致唯一的差别在于对变手势次数的限制。题目描述你可能玩过“石头剪刀布”这个游戏在奶牛中同样流行不过它的名字变成了“蹄子剪刀布”。“蹄子剪刀布”和“石头剪刀布”的规则十分类似两只奶牛数到三然后出一个代表蹄子剪刀或布的手势。蹄子胜过剪刀剪刀胜过布布胜过蹄子。特别地如果两只奶牛的手势相同则视为平局。现在 FJ 和 Bassie 要进行N NN轮对抗。Bassie 已经预测了 FJ 每一轮要出的手势。然而 Bassie 很懒她最多只想变换K KK次手势。现在请你帮 Bassie 求出她最多能赢多少轮。输入格式第一行输入两个整数N , K N,KN,K1 ≤ N ≤ 10 5 1 \leq N \leq 10^51≤N≤1050 ≤ K ≤ 20 0 \leq K \leq 200≤K≤20。接下来N NN行每行一个字母代表 FJ 这一轮出的手势。H代表蹄子HoofS代表剪刀ScissorsP代表布Paper。输出格式输出一个整数代表 Bassie 在最多变换K KK次手势的前提下最多赢多少轮。输入输出样例 #1输入 #15 1 P P H P S输出 #14P3609 动态规划状态机动态规划动态规划的状态表示dp[i][j][k]记录如下状态最多可以赢多少轮。i∈ \in∈[0,N],j∈ \in∈[0,2], 分别代表三种状态。 k ,分别代表三种状态。 k,分别代表三种状态。k\in$[0,K]表示改变过多少次手势。可以用滚动向量优化空间。predp[i],curdp[i1]。空间复杂度O(NK)动态规划的填表顺序枚举前置状态。i 0 to N-1,j 0 to 2, k 0 to K 。动态规划的转移方程每种状态都有三种新状态就是当前回合的3种手势。k1 k (j ! j1)如果k1 K 忽略。单个状态转移时间复杂度O(1)总时间复杂度O(NK)动态规划的初始值dp[0][0,1,2][0]0 其它全部是-N。动态规划的返回值dp[N]的最大值。vWin[i] 记录第i轮赢的状态。代码核心代码#includeiostream#includesstream#includevector#includemap#includeunordered_map#includeset#includeunordered_set#includestring#includealgorithm#includefunctional#includequeue#includestack#includeiomanip#includenumeric#includemath.h#includeclimits#includeassert.h#includecstring#includelist#includebitsetusingnamespacestd;templateclassT1,classT2std::istreamoperator(std::istreamin,pairT1,T2pr){inpr.firstpr.second;returnin;}templateclassT1,classT2,classT3std::istreamoperator(std::istreamin,tupleT1,T2,T3t){inget0(t)get1(t)get2(t);returnin;}templateclassT1,classT2,classT3,classT4std::istreamoperator(std::istreamin,tupleT1,T2,T3,T4t){inget0(t)get1(t)get2(t)get3(t);returnin;}templateclassTintvectorTRead(){intn;scanf(%d,n);vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){cinret[i];}returnret;}templateintN1000000classCOutBuff{public:COutBuff(){m_ppuffer;}templateclassTvoidwrite(T x){intnum[28],sp0;if(x0)*m_p-,x-x;if(!x)*m_p48;while(x)num[sp]x%10,x/10;while(sp)*m_pnum[sp--]48;AuotToFile();}voidwritestr(constchar*sz){strcpy(m_p,sz);m_pstrlen(sz);AuotToFile();}inlinevoidwrite(charch){*m_pch;AuotToFile();}inlinevoidToFile(){fwrite(puffer,1,m_p-puffer,stdout);m_ppuffer;}~COutBuff(){ToFile();}private:inlinevoidAuotToFile(){if(m_p-pufferN-100){ToFile();}}charpuffer[N],*m_p;};templateintN1000000classCInBuff{public:inlineCInBuff(){}inlineCInBuffNoperator(charch){FileToBuf();ch*S;return*this;}inlineCInBuffNoperator(intval){FileToBuf();intx(0),f(0);while(!isdigit(*S))f|(*S-);while(isdigit(*S))x(x1)(x3)(*S^48);valf?-x:x;S;//忽略空格换行return*this;}inlineCInBuffoperator(longlongval){FileToBuf();longlongx(0);intf(0);while(!isdigit(*S))f|(*S-);while(isdigit(*S))x(x1)(x3)(*S^48);valf?-x:x;S;//忽略空格换行return*this;}templateclassT1,classT2inlineCInBuffoperator(pairT1,T2val){*thisval.firstval.second;return*this;}templateclassT1,classT2,classT3inlineCInBuffoperator(tupleT1,T2,T3val){*thisget0(val)get1(val)get2(val);return*this;}templateclassT1,classT2,classT3,classT4inlineCInBuffoperator(tupleT1,T2,T3,T4val){*thisget0(val)get1(val)get2(val)get3(val);return*this;}templateclassTintinlineCInBuffoperator(vectorTval){intn;*thisn;val.resize(n);for(inti0;in;i){*thisval[i];}return*this;}templateclassTintvectorTRead(intn){vectorTret(n);for(inti0;in;i){*thisret[i];}returnret;}private:inlinevoidFileToBuf(){constintcanReadm_iWritePos-(S-buffer);if(canRead100){return;}if(m_bFinish){return;}for(inti0;icanRead;i){buffer[i]S[i];//memcpy出错}m_iWritePoscanRead;buffer[m_iWritePos]0;Sbuffer;intreadCntfread(bufferm_iWritePos,1,N-m_iWritePos,stdin);if(readCnt0){m_bFinishtrue;return;}m_iWritePosreadCnt;buffer[m_iWritePos]0;Sbuffer;}intm_iWritePos0;boolm_bFinishfalse;charbuffer[N10],*Sbuffer;};classSolution{public:intAns(constvectorchara,intK){constintNa.size();vectorintb;for(constautoch:a){if(Hch){b.emplace_back(0);}if(Sch){b.emplace_back(1);}if(Pch){b.emplace_back(2);}}vectorvectorintpre(3,vectorint(K1,-N));pre[0][0]pre[1][0]pre[2][0]0;for(inti0;iN;i){vectorvectorintcur(3,vectorint(K1,-N));for(intj0;j3;j){for(intk0;kK;k){for(intj20;j23;j2){constintk2k(j!j2);if(k2K){continue;}cur[j2][k2]max(cur[j2][k2],pre[j][k](j2b[i]));}}}pre.swap(cur);}intans0;for(constautov:pre){for(constautoi:v){ansmax(ans,i);}}returnans;}};intmain(){#ifdef_DEBUGfreopen(a.in,r,stdin);#endif// DEBUGCInBuffib;intn,k;ibnk;vectorchara(n);chartmp;for(inti0;in;i){iba[i]tmp;}#ifdef_DEBUGprintf(k%d,,k);Out(a,,a);/*Out(edge, edge); Out(que, que);*/#endif// DEBUGautoresSolution().Ans(a,k);coutres;return0;}单元测试TEST_METHOD(TestMethod1){k1,a{P,P,H,P,S};autoresSolution().Ans(a,k);AssertEx(4,res);}扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。

【动态规划】P3609 [USACO17JAN] Hoof, Paper, Scissor G

相关推荐

Python数字滤波器实战：低通、陷波与零相位处理指南

免费开源的 Czkawka 如何快速清理重复文件：完整使用指南

Calibre 电子书转换实战：3个高频场景 + 一张表选对格式

更多资讯

医学图像分割技术：U-Net架构与优化实践

Kinodynamic RRT*：带加速度约束的机器人平滑路径规划

impeccable用法精讲：从词根到搭配，彻底告别完美主义表达误区

AI架构师如何成为业务创新与技术落地的关键枢纽

C++迷宫求解：BFS最短路径与栈回溯的工程实现

Windows装Ubuntu子系统：WSL2安装、性能与排错指南

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？