分析
先考虑不用斜率优化的DP,我们可以只设一个f[i]表示前i个任务的总花费。
然后思考状态转移方程。第i个任务必定会被划分到某一个大任务中,所以它是
从前面某一个节点转移过来的(说明要枚举j),然后再思考枚举了某个j,如果
将第j+1个任务到第i个任务划分到一个部分,那么首先会有f[j]的贡献,然后
我们用前缀和记录了总用时与总费用系数(分别为sumT与sumF)
为什么要用前缀和呢? 其实刚开始我也没理解。但是想一想,题面中有一
句话叫同一组任务的结束时刻相同,于是当我们将i任务加进某一组时,那么这
一组的结束时间就会增加,而增加的量就是
sumT*(sumF[i]-sumF[j])
同时如果有了新的一组任务,那么后面的任务也会被影响(因为没有一组新任务机器就会开机,时间为s)
于是我们就能得到最普通的状态转移方恒:
f[i]=min(f[i],f[j]+sumT[i]*(sumF[i]-sumF[j])+s*(sumF[n]-sumF[j]));
然后拆开它
dp[j]=(sumT[i]+s)∗sumF[j]−sumT[i]∗sumF[i]−S∗sumF[n]+dp[i];
这时,未知数就与j有关,而(sumT[i]+s)就是斜率(设为k),但这里不同,因
为某个任务的t可能为负,也就是说在计算前缀和时,sumT[i]可能小于sumT[i-1]。
于是斜率就不是递增的。所以我们不能把队头小于当前斜率的情况删掉,因为后面
的f[i]可能会从这些情况中转移过来。而我们却把斜率大于k的点删去了,相当
于维护了队列的单调性,于是选择用二分去找某个点左边的斜率小于k而其右边的
斜率大于k,得到j这个点。而j点就是我们要寻找的最优转移点。
C++ 代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=3e5+10;
ll n,m,s,l,r;
ll f[N],q[N],sumT[N],sumF[N];
inline ll find(ll k)
{
if(l==r) return q[r];
int L=l,R=r;
while(L<R)
{
int mid=L+R>>1;
if(f[q[mid+1]]-f[q[mid]]<=k*(sumF[q[mid+1]]-sumF[q[mid]]))
L=mid+1;
else R=mid;
}
return L;
}
int main()
{
scanf("%lld%lld",&n,&s);
for (int i=1;i<=n;i++)
{
scanf("%lld%lld",&sumT[i],&sumF[i]);
sumT[i]+=sumT[i-1];sumF[i]+=sumF[i-1];
}
l=1,r=1;
for (int i=1;i<=n;i++)
{
ll p=find(s+sumT[i]);//当前斜率
f[i]=f[q[p]]-(s+sumT[i])*sumF[q[p]]+sumT[i]*sumF[i]+s*sumF[n];
while(l<r&&(f[q[r]]-f[q[r-1]])*(sumF[i]-sumF[q[r]])>=(f[i]-f[q[r]])*(sumF[q[r]]-sumF[q[r-1]]))
r--;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}
/*
由于出现负数,不能单纯维护递增的凸包,于是二分查找
某个点左边斜率小于右边斜率
*/
稍微提醒一下,现在此代码在最后一个点会爆long long wa掉。要把相乘的两个long long 转化成double类型
啊啊啊啊,巨佬,我改了半天,原来如此啊
%%%%太强了
tql
这一题在sumc[j]和f[j]的坐标系中 sumc[j]还是单调递增的 但是f[j]就不一定了吧 也就是说可能存在 ‘ . ‘ 这样的三个点 不会对结果造成影响吗
而且线的斜率也可能是负的 即 s+sumt[I]
所以并没有l++让其出队,因为负的情况要到前面的情况去找,同时为了维护其递增性,故r–让其出队
如果有问题的话就艾特我吧
你好, 我想问一下把那条判断改成这样为什么就错了 (f[i]-f[q[r-1]])(sumF[i]-sumF[q[r]])>=(f[i]-f[q[r]])(sumF[i]-sumF[q[r-1]])
我看看,做了好久了
能说一下是find函数里的还是main里面的
main里面
不好意思,现在才看见,我看看
这个的话,要看决策单调性,我的任务安排二里的题解有他的证明
看不懂啊,没注释啊啊啊
那就改吧