Luogu P2365 任务安排

解析

设 (dp_i) 表示处理完前 (i) 个时所花费的最小费用加上 (i) 因多分一组对后面产生的费用
(dp_i = dp_j + sumt_i imes (sumf_i - sumf_j) + S imes (sumf_n - sumf_j))
然后斜率优化即可（(n^2) 其实可过）
对于两个状态 (j,k)，当 (dp_j - S imes sumf_j - (dp_k - S imes sumf_k) < sumt_i) 时 (j) 更优
维护下凸壳，斜率和横坐标都单调增，单调队列简单维护即可

(Code)

#include<cstdio>
using namespace std;
typedef long long LL;

const int N = 5005;
int n , t[N] , f[N] , q[N];
LL S , st[N] , sf[N] , dp[N];

double slope(int x , int y)
{
	return 1.0 * (dp[x] - S * sf[x] - dp[y] + S * sf[y]) / (1.0 * sf[x] - sf[y]);
}

int main()
{
	scanf("%d%lld" , &n , &S);
	for(register int i = 1; i <= n; i++) 
		scanf("%d%d" , &t[i] , &f[i]) , st[i] = st[i - 1] + t[i] , sf[i] = sf[i - 1] + f[i];
	int h = 1 , t = 1;
	for(register int i = 1; i <= n; i++)
	{
		while (h < t && slope(q[h] , q[h + 1]) < st[i]) h++;
		dp[i] = dp[q[h]] + st[i] * (sf[i] - sf[q[h]]) + S * (sf[n] - sf[q[h]]);
		while (t > h && slope(q[t] , q[t - 1]) > slope(q[t] , i)) t--;
		q[++t] = i;
	}
	printf("%lld" , dp[n]);
}