P9505 『MGOI』Simple Round I | D. 魔法环题目背景最好的武器不一定最适合最适合的武器才最好。——殿堂魔法士 W题目描述小 M 面临着激发自己魂器——魔法环的任务。魔法环上有nnn个节点每个节点上都有一个魔法精灵每个魔法精灵都有一个固定的魔供值这些魔供值形成一个0∼n−10 \sim n-10∼n−1的排列。小 M 可以选择激活或不激活一个魔法精灵但为了激发魔法环必须至少激活k(≥2)k(\ge 2)k(≥2)个魔法精灵。每个魔法精灵无论是否激活都会产生附魔值对于一个被激活的魔法精灵它产生的附魔值为它的魔供值的平方。对于一个未被激活的魔法精灵它会在环上朝左右看分别看向两边最近的被激活的魔法精灵。它会选择其中魔供值较大的一个作为「目标精灵」产生的附魔值为这个「目标精灵」的魔供值与看向这个「目标精灵」时视线经过的距离的乘积。作为新手小 M 希望在激活魔法环的前提下使得所有魔法精灵的附魔值之和最小从而更好地控制魔法环的能量。输入格式第一行两个整数n,kn,kn,k。第二行nnn个整数表示每个节点上魔法精灵的魔供值。输出格式一行一个整数表示最小附魔值之和。输入输出样例 #1输入 #15 2 3 0 1 4 2输出 #17输入输出样例 #2输入 #210 3 2 0 1 5 8 3 4 9 6 7输出 #253说明/提示【样例 1 解释】激活魔供值为000和111的魔法精灵。魔供值为333的魔法精灵选择魔供值为111的魔法精灵产生的附魔值为1×331 \times 3 31×33。魔供值为000的魔法精灵被激活产生的附魔值为0200^20020。魔供值为111的魔法精灵被激活产生的附魔值为1211^21121。魔供值为444的魔法精灵选择魔供值为111的魔法精灵产生的附魔值为1×111 \times 1 11×11。魔供值为222的魔法精灵选择魔供值为111的魔法精灵产生的附魔值为1×221 \times 2 21×22。总共产生的附魔值为777。【数据范围】本题采用 Subtask 捆绑测试。对于所有数据2≤k≤n≤30002\le k \le n \le 30002≤k≤n≤3000k≤100k \le 100k≤100每个节点上魔法精灵的魔供值形成一个0∼n−10\sim n-10∼n−1的排列。Subtasknnnk≤k\lek≤分值111101010101010131313222100100100100100100171717333300300300100100100212121444100010001000100100100232323555300030003000100100100262626C实现#includebits/stdc.husingnamespacestd;constintN3010,M105;intp[N],q[N];longlongdp[N][M];inlinelonglongval(intpl,intpr){intcnt(pr-pl-1)*(pr-pl)1;return1ll*max(p[pl],p[pr])*cntp[pr]*p[pr];}intmain(){intn,m,pos;scanf(%d%d,n,m);for(inti1;in;i)scanf(%d,q[i]);for(inti1;in;i)if(!q[i])posi;for(inti1;in;i)p[i]q[(ipos-1-1)%n1];memset(dp,127,sizeof(dp));dp[1][1]0;for(inti1;in;i){for(intj2;jmin(i,m);j){for(intk1;ki;k){dp[i][j]min(dp[i][j],dp[k][j-1]val(k,i));if(jm)dp[i][j]min(dp[i][j],dp[k][j]val(k,i));}}}longlongansLLONG_MAX;for(inti1;in;i)ansmin(ans,dp[i][m]val(i,n1));printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3348）用C++实现信奥题 P9505 『MGOI』Simple Round I | D. 魔法环
P9505 『MGOI』Simple Round I | D. 魔法环题目背景最好的武器不一定最适合最适合的武器才最好。——殿堂魔法士 W题目描述小 M 面临着激发自己魂器——魔法环的任务。魔法环上有nnn个节点每个节点上都有一个魔法精灵每个魔法精灵都有一个固定的魔供值这些魔供值形成一个0∼n−10 \sim n-10∼n−1的排列。小 M 可以选择激活或不激活一个魔法精灵但为了激发魔法环必须至少激活k(≥2)k(\ge 2)k(≥2)个魔法精灵。每个魔法精灵无论是否激活都会产生附魔值对于一个被激活的魔法精灵它产生的附魔值为它的魔供值的平方。对于一个未被激活的魔法精灵它会在环上朝左右看分别看向两边最近的被激活的魔法精灵。它会选择其中魔供值较大的一个作为「目标精灵」产生的附魔值为这个「目标精灵」的魔供值与看向这个「目标精灵」时视线经过的距离的乘积。作为新手小 M 希望在激活魔法环的前提下使得所有魔法精灵的附魔值之和最小从而更好地控制魔法环的能量。输入格式第一行两个整数n,kn,kn,k。第二行nnn个整数表示每个节点上魔法精灵的魔供值。输出格式一行一个整数表示最小附魔值之和。输入输出样例 #1输入 #15 2 3 0 1 4 2输出 #17输入输出样例 #2输入 #210 3 2 0 1 5 8 3 4 9 6 7输出 #253说明/提示【样例 1 解释】激活魔供值为000和111的魔法精灵。魔供值为333的魔法精灵选择魔供值为111的魔法精灵产生的附魔值为1×331 \times 3 31×33。魔供值为000的魔法精灵被激活产生的附魔值为0200^20020。魔供值为111的魔法精灵被激活产生的附魔值为1211^21121。魔供值为444的魔法精灵选择魔供值为111的魔法精灵产生的附魔值为1×111 \times 1 11×11。魔供值为222的魔法精灵选择魔供值为111的魔法精灵产生的附魔值为1×221 \times 2 21×22。总共产生的附魔值为777。【数据范围】本题采用 Subtask 捆绑测试。对于所有数据2≤k≤n≤30002\le k \le n \le 30002≤k≤n≤3000k≤100k \le 100k≤100每个节点上魔法精灵的魔供值形成一个0∼n−10\sim n-10∼n−1的排列。Subtasknnnk≤k\lek≤分值111101010101010131313222100100100100100100171717333300300300100100100212121444100010001000100100100232323555300030003000100100100262626C实现#includebits/stdc.husingnamespacestd;constintN3010,M105;intp[N],q[N];longlongdp[N][M];inlinelonglongval(intpl,intpr){intcnt(pr-pl-1)*(pr-pl)1;return1ll*max(p[pl],p[pr])*cntp[pr]*p[pr];}intmain(){intn,m,pos;scanf(%d%d,n,m);for(inti1;in;i)scanf(%d,q[i]);for(inti1;in;i)if(!q[i])posi;for(inti1;in;i)p[i]q[(ipos-1-1)%n1];memset(dp,127,sizeof(dp));dp[1][1]0;for(inti1;in;i){for(intj2;jmin(i,m);j){for(intk1;ki;k){dp[i][j]min(dp[i][j],dp[k][j-1]val(k,i));if(jm)dp[i][j]min(dp[i][j],dp[k][j]val(k,i));}}}longlongansLLONG_MAX;for(inti1;in;i)ansmin(ans,dp[i][m]val(i,n1));printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
