热门
最新
红包
立Flag
投票
同城
我的
发布
《洛谷 P9505 『MGOI』Simple Round I | D. 魔法环 题解》
题目摘要：给定一个长度为n的环形排列，要求选择至少2个点激活。激活点的贡献为其值的平方，未激活点的贡献为两侧激活点较大值乘以距离。求最小总贡献。 解题思路：通过断环成链，以最小值0作为断点简化问题。使用动态规划，定义dp[i][j]表示前i个数激活至少j个的最小贡献。转移方程考虑激活点间的贡献计算，最终在dp[i][k]基础上加上剩余部分的贡献得到答案。时间复杂度为O(n^2k)。
——来自博客 https://blog.csdn.net/2301_80005273/article/details/157938652
懂了吗(单选)
0 人已经参与 已结束
懂了
0人
没懂
0人
CSDN App 扫码分享
评论
点赞
- 复制链接
- 举报
