斜率DP-凸壳优化策略（convex hull trick）&&POJ1180&&CODEVS-1319

何为斜率dp：

与一般的单调队列优化DP的模型相比 ，斜率DP维护的是依赖于队列中相邻的两个元素之间的某种比值。因为这个值对应线性规划的坐标系中的斜率，所以我们称之为斜率优化

POJ1180

题意：有N个任务排成一个序列在一台机器上等待执行，他们的顺序不得改变。机器会把这N个任务分成若干批，每一批包含连续的若干个任务。从时刻0开始，任务被分批加工，执行第i个任务所需的时间是Ti。另外，在每批任务开始之前，机器需要S的启动时间，故执行一批任务所需要的时间是启动时间S加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务执行全部完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是他完成时刻乘以费用系数Ci。求得一个方案 让总费用最小。

思路：

设F[i]把前i个任务分成若干批次所需要的最小费用

sumT[i]是忽略启动时间，这批任务的完成时刻。sumC[i] = 

F[I]=min(F[J]+(SUMC[i]-SUMC[j])*S+SUMT[i]*(SUMC[i]-SUMC[j]))

这里用的是费用延迟的做法 没有直接算出每批任务的完成时刻，而是在一批任务“开始”后，计算对这批任务以及后续任务的影响，把费用累加到答案里。

然后把上式化简得F[j]=(S+sumT[i])*sumC[j]+F[i]-sumT[i]*sumC[i]-S*sumC[N];

然后以sumC[j]为横坐标 F[j]为纵坐标建系.也就是说这是一条以（S+sumT[i]）为斜率，F[i]-sumT[i]*sumC[i]-S*sumC[N]为截距的直线，决策候选集合就是坐标系的每一个点集，每个带求解的状态F[i]都对应的一个直线的截距，因为（sumT[i]*sumC[i]-S*sumC[N）都是定值，所以截距最小的时候F[i]达到最小！

由此就把该问题转化成了一个线性规划的问题，应该是高中数学了，用一条斜率是固定正整数的直线自下而上平移，第一次接触到某个决策点时，就得到了最小截距

这种题的解法就是用斜率为固定整数的直线从下而上去找截距最小的点，一个找到的点就是截距最小的点。

对于任意三个决策点j1,j2,j3来说,我们不妨设j1<j2<j3,且T,C,均为正整数，根据即使派出无用策略的思想，我们来考虑j2有可能成为最有决策的条件

由此我们发现j2可能成为最有决策当且仅当：

不等号两端连接两个决策点的斜率

整体来看我们应该维护："连接相邻两点的线段斜率"，单调递增的一个下凸壳，只有这个下凸壳的定点才有可能成为最有决策。

因为sumT的单调性，每次求解最小截距的直线斜率S+sumt[i]也单调递增，如果我们只保留凸壳上连接相邻两点的线段斜率大于S+sumT[i]的部分，那么凸壳的最左端顶点一定是最优决策.

综上所述：

对于每个决策i

1.检查队头的两个决策变量q[l]和q[l+1]，若斜率(f[q[l+1]-f[q[l]]])/(sumc[q[l+1]]-sumc[q[l]])<=s+sumt[i],则把q[l]移出队列，继续检查新的队头元素（这里是说q[l+1]是比q[l]更优的决策）

2.直接取队头j=q[l]为最优决策,执行状态转移.计算出F[i]

3.把新决策i从队尾插入队中，在插入之前，检查q[r-1],q[r]和i是否满足下凸性，及q[l]是否是无用决策,若是则把q[r]出队,继续检查新的队尾.

code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#pragma warning(disable:4996)
using namespace std;

typedef long long ll;
typedef double db;
const int maxn = 100100;
int n, s;
int dp[maxn];
int q[maxn];
int sumt[maxn];
int sumc[maxn];

int main()
{
	cin >> n >> s;
	memset(sumc, 0, sizeof(sumc));
	memset(sumt, 0, sizeof(sumt));
	for (int i = 1; i <= n; i++)
	{
		int t, c;
		scanf("%d%d",&t,&c);
		sumt[i] = sumt[i - 1] + t;
		sumc[i] = sumc[i - 1] + c;
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	int l = 1, r = 1;
	q[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		while (l < r && (dp[q[l + 1]] - dp[q[l]]) <= (s + sumt[i])*(sumc[q[l + 1]] - sumc[q[l]]))l++;
		dp[i] = dp[q[l]] - (s + sumt[i])*sumc[q[l]]+sumc[i]*sumt[i]+sumc[n]*s;
		while (l < r && (dp[q[r]] - dp[q[r - 1]])*(sumc[i] - sumc[q[r]]) >= (dp[i] - dp[q[r]])*(sumc[q[r]] - sumc[q[r - 1]]))r--;
		q[++r] = i;
	}
	cout << dp[n] << endl;
	system("pause");
	return 0;
}