本文涉及知识点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**实现。