山西网站推广公司,广州做网站好的公司,如何把网站上线,上海网站设计 企业斜率优化
一、简单DP
首先从一道简单题引入。
[IOI2002]任务安排
Description
N个任务排成一个序列在一台机器上等待完成#xff08;顺序不得改变#xff09;#xff0c;这N个任务被分成若干批#xff0c;每批包含相邻的若干任务。从时刻0开始#xff0c;这些任务被分…斜率优化
一、简单DP
首先从一道简单题引入。
[IOI2002]任务安排
Description
N个任务排成一个序列在一台机器上等待完成顺序不得改变这N个任务被分成若干批每批包含相邻的若干任务。从时刻0开始这些任务被分批加工第i个任务单独完成所需的时间是Ti。在每批任务开始前机器需要启动时间S而完成这批任务所需的时间是各个任务需要时间的总和同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数ci。请确定一个分组方案使得总费用最小。
例如S1T{1,3,4,2,1}F{3,2,3,3,4}。如果分组方案是{1,2}、{3}、{4,5}则完成时间分别为{5,5,10,14,14}费用C{15,10,30,42,56}总费用就是153。
Input
第一行是N(1N5000)。
第二行是S(0S50)。
下面N行每行有一对数分别为Ti和ci均为不大于100的正整数表示第i个任务单独完成所需的时间是Ti及其费用系数ci。
Output
一个数最小的总费用。
Sample Input
5
1
1 3
3 2
4 3
2 3
1 4
Sample Output
153
Solution
“光着身子”的动态规划。
设F[i,j]表示划分前i个任务为j批的最小费用。 时间复杂度空间复杂度
这显然是不够的。 实际上我们不一定要知道之前划分了多少批任务只需要记录F[i]表示划分前i个任务的最小费用。 这样就写出了动态规划方程。
二、简单题2
将上题的n5000改为n300000。
Solution
这就是本文的重点所在了。
在上文中的动态规划中尚有两种简单的优化思路
优化状态将这样一个动态规划转化为贪心或数学题。优化转移优化转移的时间主要为优化重复或不必要的转移。
显然优化状态很难达成那么我们考虑优化转移。
我们可以发现在转移的过程中有很多的不必要的转移
考虑一下两个转移: 在此题中若
那么转移 j 就是不必要的。
也就是说若有且选取转移状态的集合
并且存在后面的转移比前面的优则前面的转移就是无意义的也就是对最终答案无贡献的了。 考虑本题如何判断转移状态是否是有用的呢 也就是说如果
那么后面的转移比前面的优否则前面的转移比后面的优。
这样的即是用斜率的形式表现了转移之间的不必要的关系。 进一步我们发现 也就是说如果当前存在后面的转移比前面的优那么这个转移在之后的状态中都不会成为最有转移
根据这个性质我们选择用单调队列维护一个两点间斜率单调递增的点集队列。
设 若有 则的转移必然不会是最优的于是能够将它删除。维护队尾若有 则x1的转移必然不会是最优的于是能够将它删除。 维护队首
最后的点集队列满足在队首的点的转移必然是最优的。
于是
将转移化为动态规划完成。
三、简单题3
若 -512t[i]512 也就是说 不再成立怎么办呢
我们发现
若有 则的转移必然不会是最优的于是能够将它删除。维护队尾
这一性质依然成立那么这个点集集合还是会组成一个相邻点斜率递增的单调队列。
有
发现
如果那么优于。如果那么优于。
也就是说答案一定存在于一个点使得 且
那么必然最优。
我们可以维护单调队列只在队尾删除每次二分查询一个最优点。
这样便是的斜率优化做法。 四、简单题4
一种形式斜率优化的形式
队列中的点不满足单调性。
BZOJ1492: [NOI2007]货币兑换Cash
题目描述详见BZOJ。
这一题就是典型的例子。
斜率不单调那么就必须用cdq分治或splay维护斜率凸包解决斜率优化问题了。
下次有时间再补充。。。
