自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:49:00，当前版本为作者最后更新于2023-08-06 21:33:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

DP 做法

这道题可以用 DP 做，也是一类分段问题。

我们知道这道题的元素构成了一个环，没法直接 DP，考虑以魔供值为 $0$ 的精灵为断点，并激活，将环断成链。

为什么可以这么做呢？因为将魔供值为 $0$ 的精灵激活，它周围的未被激活的精灵肯定不会选择它作「目标精灵」，要是选魔供值大于 $0$ 的，魔供值的平方会更大，还有可能会让周围的未被激活的精灵选择它作「目标精灵」，导致答案变大，所以说将魔供值为 $0$ 的精灵激活一定不会劣于其他方案。

那么我们照上述方法将环断成链，设该链上精灵的魔供值从左往右依次为为 $p_1,p_2,\ldots p_n$，其中 $p_1=0$。

设 $dp_{i,j}$ 表示将第 $i$ 个精灵激活，前 $i$ 个精灵中激活 $j$ 个精灵产生的附魔值之和的最小值，那么不难得出以下状态转移方程：

$$dp_{i,j}=\min_{k=1}^{i-1}dp_{k,j-1}+val(k,i)~(1\le j\le i\le n,j\le m) $$

其中 $val(k,i)$ 表示第 $i$ 和 $k$ 个精灵已被激活，中间未被激活的精灵与第 $i$ 个精灵的附魔值之和，计算方式为：

$$val(k,i)=\max(p_k,p_i)\times\dfrac{(i-k-1)(i-k)}{2}+{p_i}^2 $$

不过题目中说的是至少选 $m$ 个精灵激活，为了节省时空复杂度，我们将 $dp_{i,m}$ 的定义改为将第 $i$ 个精灵激活，前 $i$ 个精灵中激活 至少 $m$ 个精灵产生的附魔值之和的最小值，那么需要给 $dp_{i,m}$ 附加一个状态转移方程：

$$dp_{i,m}=\min_{k=1}^{i-1}dp_{k,m}+val(k,i)~(1\le m\le i\le n) $$

不过千万别忘了赋初始值，首先，将所有 $dp_{i,j}$ 置为 $+\infty$，之后，将 $dp_{1,1}$ 置 $0$，因为断成链后第 $1$ 个精灵魔供值就为 $0$，正是我们必定激活的那个，$dp_{1,1}$ 的值又全由它决定，所以 $dp_{1,1}={p_1}^2=0^2=0$。

代码实现

#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){
// 不用 inline 连吸氧都卡不过
	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;
}