题意:
给出n, c,长度为n的数组
划分数组,子数组中 倒数第1小 到 倒数第 $\lfloor \frac {子数组长度}{c} \rfloor$小 的元素删掉
除了删除的元素,全部加起来(全部)
问这个加起来的值最小是多少
解法:
子数组的长度尽量划分成c
长度小于c时,明显就不能删除
长度大于c时,
假设长度划分为2
下图可能的情况(将原本要划分为两个长度为c的子数组,当一个长度为2c的子数组)
所以划分出2c的子数组比划分出c的子数组的 结果 可能更差
具体:
使用动态规划
dp[i]: 代表使用1~i个元素,最小值是dp[i]
转移方程: dp[i] = min(dp[i-1] + a[i], dp[i-c] - pre[i] - pre[i-c] - min(a[i-c]~a[i]))
a[i]就是题目给出的原数组
pre[i]就是第i位的前缀和
这个转移方程的意思就是:
第i个元素和前i-1个元素
第i-c+1到第i个元素(其中删除一个最小的元素(题目要求)),当成一个子数组
比较下哪值个小
使用multiset维护i-c+1到i的最小值
代码:
1 |
|