任务安排 1~3 Solute&Code
jur10n
·
·
个人记录
1
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];
}
2
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];
}
3
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];
}