P9505 『MGOI』Simple Round I | D. 魔法环

题目背景

最好的武器不一定最适合，最适合的武器才最好。——
殿堂魔法士 W

题目描述

小 M 面临着激发自己魂器——魔法环的任务。

魔法环上有 $n$ 个节点，每个节点上都有一个魔法精灵，每个魔法精灵都有一个固定的魔供值，这些魔供值形成一个 $0\sim n-1$ 的排列。

小 M 可以选择激活或不激活一个魔法精灵，但为了激发魔法环，必须至少激活 $k(\ge 2)$ 个魔法精灵。

每个魔法精灵无论是否激活都会产生附魔值：

• 对于一个被激活的魔法精灵，它产生的附魔值为它的魔供值的平方。
• 对于一个未被激活的魔法精灵，它会在环上朝左右看，分别看向两边最近的被激活的魔法精灵。它会选择其中魔供值较大的一个作为「目标精灵」，产生的附魔值为这个「目标精灵」的魔供值与看向这个「目标精灵」时视线经过的距离的乘积。

作为新手，小 M 希望在激活魔法环的前提下，使得所有魔法精灵的附魔值之和最小，从而更好地控制魔法环的能量。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数，表示每个节点上魔法精灵的魔供值。

输出格式

一行一个整数，表示最小附魔值之和。

输入输出样例 #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 解释】

激活魔供值为 $0$ 和 $1$ 的魔法精灵。

• 魔供值为 $3$ 的魔法精灵，选择魔供值为 $1$ 的魔法精灵，产生的附魔值为 $1\times 3=3$。
• 魔供值为 $0$ 的魔法精灵被激活，产生的附魔值为 $0^2=0$。
• 魔供值为 $1$ 的魔法精灵被激活，产生的附魔值为 $1^2=1$。
• 魔供值为 $4$ 的魔法精灵，选择魔供值为 $1$ 的魔法精灵，产生的附魔值为 $1\times 1=1$。
• 魔供值为 $2$ 的魔法精灵，选择魔供值为 $1$ 的魔法精灵，产生的附魔值为 $1\times 2=2$。

总共产生的附魔值为 $7$。

【数据范围】

本题采用 Subtask 捆绑测试。

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

Subtask	$n$	$k\le$	分值
$1$	$10$	$10$	$13$
$2$	$100$	$100$	$17$
$3$	$300$	$100$	$21$
$4$	$1000$	$100$	$23$
$5$	$3000$	$100$	$26$

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=3010,M=105;
int p[N],q[N]; long long dp[N][M];
inline long long val(int pl,int pr){
	int cnt=(pr-pl-1)*(pr-pl)>>1;
	return 1ll*max(p[pl],p[pr])*cnt+p[pr]*p[pr];
}
int main(){
	int n,m,pos;scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
		scanf("%d",&q[i]);
	for(int i=1;i<=n;i++) 
		if(!q[i]) 
			pos=i;
	for(int i=1;i<=n;i++) 
		p[i]=q[(i+pos-1-1)%n+1];
	memset(dp,127,sizeof(dp)); dp[1][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=2;j<=min(i,m);j++){
			for(int k=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));
			}
		}
	} 
	long long ans=LLONG_MAX;
	for(int i=1;i<=n;i++) 
		ans=min(ans,dp[i][m]+val(i,n+1));
	printf("%lld",ans);   return 0;
}

后续

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