P11876 [威海市赛2024] 收徒题目描述小威和小海正在玩《铁斧斧之争》。小威给小海狠狠上了一课在这局游戏中获得了第一名。小威很兴奋大喊收徒小海很不服给他提了一个问题并且要求他解决不然就再也不和他玩了。小威立马同意了。问题是这样的在《铁斧斧之争》中有一个HHH行WWW列的棋盘令(i,j)(i, j)(i,j)表示从上往下数第iii行从左往右数第jjj列的单元格。在这个棋盘中分布着NNN个棋子当小威经过(Ri,Ci)(R_i, C_i)(Ri​,Ci​)格时可以获得第iii个棋子获得111的战斗力。小海想知道如果小威从(1,1)(1, 1)(1,1)开始反复向下或向右移动一个格子最终到达(H,W)(H, W)(H,W)时能最多获得多少战斗力小威立马秒了但小海捂住了他的嘴继续说除此之外我还想知道你是如何获得最多战斗力的你还要告诉我获得最多战斗力的这条路径。小威“……”你能帮帮他吗输入格式第一行三个整数H,W,NH, W, NH,W,N含义如上所述接下来NNN行每行两个整数Ri,CiR_i, C_iRi​,Ci​含义如上所述。对于所有数据满足2≤H,W≤2×1052 \leq H, W \leq 2 \times 10^52≤H,W≤2×1051≤N≤min⁡(HW−2,2×105)1 \leq N \leq \min(HW - 2, 2 \times 10^5)1≤N≤min(HW−2,2×105)1≤Ri≤H1 \leq R_i \leq H1≤Ri​≤H1≤Ci≤W1 \leq C_i \leq W1≤Ci​≤W(Ri,Ci)≠(1,1)(R_i, C_i) \neq (1, 1)(Ri​,Ci​)(1,1)(Ri,Ci)≠(H,W)(R_i, C_i) \neq (H, W)(Ri​,Ci​)(H,W)(Ri,Ci)(R_i, C_i)(Ri​,Ci​)互不相同。输出格式输出两行。第一行一个整数表示你能获得的最大战斗力第二行一个长度为HW−2HW-2HW−2的字符串如果第iii次移动是向下的则字符串的第iii个字符为D如果第iii次移动是向右的则字符串的第iii个字符为R。如果有多条路径可以最大化获得的战斗力则输出任意一条路径即可。输入输出样例 #1输入 #13 4 4 1 4 2 1 2 3 3 3输出 #13 DRRDR说明/提示对于第一组样例一种可行的方案如下图所示移动路径为(1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(3,4)(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (3, 3) \to (3, 4)(1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(3,4)可以在(2,1),(2,3),(3,3)(2, 1), (2, 3), (3, 3)(2,1),(2,3),(3,3)处得到三个棋子。C实现#includebits/stdc.husingnamespacestd;constintN2e510;inth,w,n,num[N],tot,idd[N];structnode{intx,y,id,fr;}a[N];boolcmp(node a,node b){if(a.yb.y)returna.xb.x;returna.yb.y;}voiddfs(intx){if(a[x].fr)dfs(a[x].fr);node va[a[x].fr];for(intiv.x;ia[x].x;i)coutR;for(intiv.y;ia[x].y;i)coutD;}intmain(){cinhwn;a[0].xa[0].y1;for(inti1;in;i){cina[i].ya[i].x;}sort(a1,an1,cmp);for(inti1;in;i){a[i].idi;if(a[i].xnum[tot]){a[i].fridd[tot];idd[tot]i;num[tot]a[i].x;}else{intxupper_bound(num1,numtot1,a[i].x)-num;idd[x]i;a[i].fridd[x-1];num[x]a[i].x;}}couttot\n;a[n1]{w,h,0,idd[tot]};dfs(n1);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容