任务安排 1~3 Solute&Code

class Solotion_Case
{
	/*
	首先考虑最基本的思路：
	先求出s,t的前缀和，然后设f[i,j]表示把前i个任务分成j批执行的最小费用
	这样就可以列出n三次方的方程，见algo P352

	来一个小优化：
	由于本题目没有规定需要把任务分成多少批次，在上一个解法之中之所以需要批数j，
	是因为我们需要知道机器启动了多少次，从而计算出当前任务的完成时刻，那么考虑能否直接获取每个任务执行时候的开始时间
	⭐机器执行某一批任务而花费的启动时间S，会累加到在此之后所有任务的完成时刻上面。
	设f[i]表示把前i个任务分成若干批执行的最小费用，有方程：
	f[i] = min{ f[j] + sumT[i]*(sumC[i]-sumC[j]) + S*(sumC[N]-sumC[j]) }，其中0 ≤ j＜i，sumT[i]是忽略机器的启动时间时，这批任务的完成时刻

	*/
};
#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define inf 0x3f
using namespace std;
class Quick_IO
{
  public:
	template<typename T>
	void read(T &r)
	{
		T x = 0, f = 1;
		char ch = getchar();
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = -1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
		r = x * f;
	}
	template<typename T, typename... Args>
	void read(T &tmp, Args &... tmps)
	{
		read(tmp);
		read(tmps...);
	}
} io;

int n, S;
ll f[N], st[N], sc[N];
#define sumc(i,j) (sc[i] - sc[j]) //注意！！define直接把代码移下来，需要加括号

signed main()
{
	io.read(n, S);
	for (int i = 1, t, c; i <= n; i++)
	{
		io.read(t, c);
		st[i] = st[i - 1] + t;
		sc[i] = sc[i - 1] + c;
	}

	memset(f, inf, sizeof f);
	f[0] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < i; j++)
			f[i] = min(f[i], f[j] + st[i] * sumc(i, j) + S * sumc(n, j));

	cout << f[n];
}

class Solotion_Case
{
	/*
	基本思路见任务安排1，注意本题T1的n方代码即可过。

	1.考虑优化：
	先把方程拆开成多项式，去掉min，把关于j的值看作变量，其余部分看作常数
		f[j] = ( S+sumT[i] ) * sumC[j] + { f[i] - sumT[i]*sumC[i] - S*sumC[N] }
		可以得到：k=( S+sumT[i] )；b={ f[i] - sumT[i]*sumC[i] - S*sumC[N] }
	因此每个决策的点都对应着坐标系的一个点(sumC[j],f[j])；每个待求解的状态f[i]都对应着一条直线的截距，而斜率固定
	目的是找到最小截距（k定，平移线段）

	2.
	由于前缀和的单调性（体现在坐标中x,y的单调性），我们只需要维护一个点集合，满足任意三个点都符合下凸关系
	即维护一个凸壳，这样凸壳的最左边的端点（也是最低的），就是最小的截距对应的线过的点
	因为对于每个需要求解的状态来说，斜率是递增的。

	3.
	因此可以使用单调队列来维护球壳，满足球壳里面最低两点的斜率大于这个状态的斜率，来让最左点符合条件
	考虑维护这个队列：
		每次i++，都会加入一个新的决策点到坐标系上，同时斜率增大。
		最左边的点如果和下一个点的斜率小于当前要求解的状态斜率，说明不符合要求，那么删左边直到符合要求（出队）。
		这时候最左边的点就是最优解，直接更新状态。
		然后把新决策放在右面（队尾），注意这个操作也需要维护：
		如果右面放了以后不符合凸壳，也就是说这个要加入的点的斜率比目前最右边的点要更小（点更低），那么把队尾出队直到满足凸壳。

	非常妙的思路！！
	复杂度:N
	*/
};
#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define inf 0x3f
using namespace std;
class Quick_IO
{
  public:
	template<typename T>
	void read(T &r)
	{
		T x = 0, f = 1;
		char ch = getchar();
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = -1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
		r = x * f;
	}
	template<typename T, typename... Args>
	void read(T &tmp, Args &... tmps)
	{
		read(tmp);
		read(tmps...);
	}
} io;

int n, S;
ll f[N], st[N], sc[N];
int q[N];

signed main()
{
	io.read(n, S);
	for (int i = 1, t, c; i <= n; i++)
	{
		io.read(t, c);
		st[i] = st[i - 1] + t;
		sc[i] = sc[i - 1] + c;
	}

	memset(f, inf, sizeof f);
	f[0] = 0;
	int l = 1, r = 1;
	q[1] = 0;

	for (int i = 1; i <= n; i++)
	{
		while (l < r && (f[q[l + 1]] - f[q[l]]) <= (S + st[i]) * (sc[q[l + 1]] - sc[q[l]])) l++;	//除法移项变乘
		int j = q[l];
		f[i] = f[j] - (S + st[i]) * sc[j] + st[i] * sc[i] + S*sc[n];
		while (l < r && (f[q[r]] - f[q[r - 1]]) * (sc[i] - sc[q[r]]) >= (f[i] - f[q[r]]) * (sc[q[r]] - sc[q[r - 1]])) r--;
		q[++r] = i;
	}

	cout << f[n];
}

class Solotion_Case
{
	/*
	在T2的基础上，我们发现任务的执行时间可能是负数，意味着斜率不再具有单调性。
	所以我们不能只在单调队列上维护比当前斜率大的点，而是应该维护一个完整的凸壳。
	这样的话队头就不一定是最优的选择了，可以在整个点集里面二分查找最合适的位置，
	让这个位置满足左侧线段的斜率比S+sumT[i]小，右侧线段的斜率比他大，就是在当前待求解直线以上的最凸点
	队尾维护的方法同T2。

	复杂度O(NlogN)
	*/
};
#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define inf 0x3f
using namespace std;
class Quick_IO
{
  public:
	template<typename T>
	void read(T &r)
	{
		T x = 0, f = 1;
		char ch = getchar();
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = -1;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
		r = x * f;
	}
	template<typename T, typename... Args>
	void read(T &tmp, Args &... tmps)
	{
		read(tmp);
		read(tmps...);
	}
} io;

int n, S;
ll f[N], st[N], sc[N];
int q[N], l, r;

int Binary_Search(int i, int k)
{
	if (l == r) return q[l];
	int L = l, R = r;
	while (L < R)
	{
		int mid = (L + R) / 2;
		if (f[q[mid + 1]] - f[q[mid]] <= k * (sc[q[mid + 1]] - sc[q[mid]])) L = mid + 1;
		else R = mid;
	}
	return q[L];
}

signed main()
{
	io.read(n, S);
	for (int i = 1, t, c; i <= n; i++)
	{
		io.read(t, c);
		st[i] = st[i - 1] + t;
		sc[i] = sc[i - 1] + c;
	}

	memset(f, inf, sizeof f);
	f[0] = 0;
	q[1] = 0, l = 1, r = 1;

	for (int i = 1; i <= n; i++)
	{
		int j = Binary_Search(i, S + st[i]);
		f[i] = f[j] - (S + st[i]) * sc[j] + st[i] * sc[i] + S*sc[n];
		while (l < r && (f[q[r]] - f[q[r - 1]]) * (sc[i] - sc[q[r]]) >= (f[i] - f[q[r]]) * (sc[q[r]] - sc[q[r - 1]])) r--;
		q[++r] = i;
	}

	cout << f[n];
}