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

· · 题解

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;
}