打卡信奥刷题（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

输入 #1

5 2 3 0 1 4 2

输出 #1

7

输入输出样例 #2

输入 #2

10 3 2 0 1 5 8 3 4 9 6 7

输出 #2

53

说明/提示

【样例 1 解释】

激活魔供值为000和111的魔法精灵。

• 魔供值为333的魔法精灵，选择魔供值为111的魔法精灵，产生的附魔值为1×3=31 \times 3 = 31×3=3。
• 魔供值为000的魔法精灵被激活，产生的附魔值为02=00^2=002=0。
• 魔供值为111的魔法精灵被激活，产生的附魔值为12=11^2=112=1。
• 魔供值为444的魔法精灵，选择魔供值为111的魔法精灵，产生的附魔值为1×1=11 \times 1 = 11×1=1。
• 魔供值为222的魔法精灵，选择魔供值为111的魔法精灵，产生的附魔值为1×2=21 \times 2 = 21×2=2。

总共产生的附魔值为777。

【数据范围】

本题采用 Subtask 捆绑测试。

对于所有数据，2≤k≤n≤30002\le k \le n \le 30002≤k≤n≤3000，k≤100k \le 100k≤100，每个节点上魔法精灵的魔供值形成一个0∼n−10\sim n-10∼n−1的排列。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=3010,M=105;intp[N],q[N];longlongdp[N][M];inlinelonglongval(intpl,intpr){intcnt=(pr-pl-1)*(pr-pl)>>1;return1ll*max(p[pl],p[pr])*cnt+p[pr]*p[pr];}intmain(){intn,m,pos;scanf("%d%d",&n,&m);for(inti=1;i<=n;i++)scanf("%d",&q[i]);for(inti=1;i<=n;i++)if(!q[i])pos=i;for(inti=1;i<=n;i++)p[i]=q[(i+pos-1-1)%n+1];memset(dp,127,sizeof(dp));dp[1][1]=0;for(inti=1;i<=n;i++){for(intj=2;j<=min(i,m);j++){for(intk=1;k<i;k++){dp[i][j]=min(dp[i][j],dp[k][j-1]+val(k,i));if(j==m)dp[i][j]=min(dp[i][j],dp[k][j]+val(k,i));}}}longlongans=LLONG_MAX;for(inti=1;i<=n;i++)ans=min(ans,dp[i][m]+val(i,n+1));printf("%lld",ans);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容