{"problem":{"name":"『MGOI』Simple Round I | D. 魔法环","description":{"content":"小 M 面临着激发自己魂器——魔法环的任务。 魔法环上有 $n$ 个节点，每个节点上都有一个魔法精灵，每个魔法精灵都有一个固定的**魔供值**，这些魔供值形成一个 $0 \\sim n-1$ 的排列。 小 M 可以选择激活或不激活一个魔法精灵，但为了激发魔法环，必须**至少**激活 $k(\\ge 2)$ 个魔法精灵。 每个魔法精灵无论是否激活都会产生**附魔值**： - 对于一个被激活的魔法","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9505"},"statements":[{"statement_type":"Markdown","content":"小 M 面临着激发自己魂器——魔法环的任务。\n\n魔法环上有 $n$ 个节点，每个节点上都有一个魔法精灵，每个魔法精灵都有一个固定的**魔供值**，这些魔供值形成一个 $0 \\sim n-1$ 的排列。\n\n小 M 可以选择激活或不激活一个魔法精灵，但为了激发魔法环，必须**至少**激活 $k(\\ge 2)$ 个魔法精灵。\n\n每个魔法精灵无论是否激活都会产生**附魔值**：\n\n- 对于一个被激活的魔法精灵，它产生的附魔值为它的魔供值的**平方**。\n- 对于一个未被激活的魔法精灵，它会在环上朝左右看，分别看向两边最近的被激活的魔法精灵。它会选择其中魔供值较大的一个作为「目标精灵」，产生的附魔值为这个「目标精灵」的魔供值与**看向这个「目标精灵」时视线经过的距离**的**乘积**。\n\n作为新手，小 M 希望在激活魔法环的前提下，使得所有魔法精灵的附魔值之和最小，从而更好地控制魔法环的能量。\n\n## Input\n\n第一行两个整数 $n,k$。\n\n第二行 $n$ 个整数，表示每个节点上魔法精灵的魔供值。\n\n## Output\n\n一行一个整数，表示最小附魔值之和。\n\n[samples]\n\n## Background\n\n> 最好的武器不一定最适合，最适合的武器才最好。——\n殿堂魔法士 W\n\n## Note\n\n**【样例 1 解释】**\n\n激活魔供值为 $0$ 和 $1$ 的魔法精灵。\n\n- 魔供值为 $3$ 的魔法精灵，选择魔供值为 $1$ 的魔法精灵，产生的附魔值为 $1 \\times 3 = 3$。\n- 魔供值为 $0$ 的魔法精灵被激活，产生的附魔值为 $0^2=0$。\n- 魔供值为 $1$ 的魔法精灵被激活，产生的附魔值为 $1^2=1$。\n- 魔供值为 $4$ 的魔法精灵，选择魔供值为 $1$ 的魔法精灵，产生的附魔值为 $1 \\times 1 = 1$。\n- 魔供值为 $2$ 的魔法精灵，选择魔供值为 $1$ 的魔法精灵，产生的附魔值为 $1 \\times 2 = 2$。\n\n总共产生的附魔值为 $7$。\n  \n**【数据范围】** \n\n**本题采用 Subtask 捆绑测试。**\n\n对于所有数据，$2\\le k \\le n \\le 3000$，$k \\le 100$，每个节点上魔法精灵的魔供值形成一个 $0\\sim n-1$ 的排列。 \n\n| Subtask | $n$ | $k\\le$ | 分值 |  \n| :------------: | :----------: | :----------:|:----------------:|\n| $1$ | $10$ | $10$ | $13$ |\n| $2$ | $100$ | $100$ | $17$ | \n| $3$ | $300$ | $100$ | $21$ | \n| $4$ | $1000$ | $100$ | $23$ | \n| $5$ | $3000$ | $100$ | $26$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9505","tags":["动态规划 DP","洛谷原创","O2优化"],"sample_group":[["5 2\n3 0 1 4 2","7"],["10 3\n2 0 1 5 8 3 4 9 6 7","53"]],"created_at":"2026-03-03 11:09:25"}}