P10981 任务安排 4.2【暂无数据】 题解

· · 题解

题目传送门

前置知识

斜率优化 | CDQ 分治

解法

由 luogu P10979 任务安排 2 得到基本转移方程为 f_{i}=\min\limits_{j=0}^{i-1} \{ f_{j}+sumt_{i}(sumc_{i}-sumc_{j})+s(sumc_{n}-sumc_{j}) \}，删去状态转移方程中的 \min，将 f_{j} 和 sumc_{j} 看作变量，在以 sumc_{j} 为横坐标，以 f_{j} 为纵坐标的平面直角坐标系中可以得到直线 y=kx+b，其中 \begin{cases} x=sumc_{j} \\ y=f_{j} \\ k=s+sumt_{i} \\ b=f_{i}-sumt_{i} \times sumc_{i}-s \times sumc_{n} \end{cases}。

本题中因横坐标 x 和斜率 k 都不单调递增，可以使用 CDQ 分治优化转移，具体写法同 luogu P4655 [CEOI2017] Building Bridges。

因为暂时没有数据，所以不保证代码一定正确。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
ll f[300010],t[300010],c[300010],k[300010],p[300010],tmp[300010],n,s;
deque<ll>q;
bool cmpk(ll a,ll b)
{
    return k[a]<k[b];
}
ll x(ll i)
{
    return c[i];
}
ll y(ll i)
{
    return f[i];
}
bool cmpx(ll a,ll b)
{
    return (x(a)==x(b))?(y(a)<y(b)):(x(a)<x(b));
}
void cdq(ll l,ll r)
{
    if(l==r)  return;
    ll mid=(l+r)/2;
    for(ll i=l,x=l,y=mid+1;i<=r;i++)
    {
        if(p[i]<=mid)
        {
            tmp[x]=p[i];  x++;
        }
        else
        {
            tmp[y]=p[i];  y++;
        }
    }
    for(ll i=l;i<=r;i++)  p[i]=tmp[i];
    cdq(l,mid);
    q.clear();
    for(ll i=l;i<=mid;i++)
    {
        while(q.size()>=2&&(y(q.back())-y(q[q.size()-2]))*(x(p[i])-x(q.back()))>=
                            (y(p[i])-y(q.back()))*(x(q.back())-x(q[q.size()-2])))
            q.pop_back();
        q.push_back(p[i]);
    }
    for(ll i=mid+1;i<=r;i++)
    {
        while(q.size()>=2&&(y(q[1])-y(q.front()))<=k[p[i]]*(x(q[1])-x(q.front())))
            q.pop_front();
        f[p[i]]=min(f[p[i]],f[q.front()]+t[p[i]]*(c[p[i]]-c[q.front()])+s*(c[n]-c[q.front()]));
    }
    cdq(mid+1,r);
    sort(p+l,p+r+1,cmpx);
}
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>n>>s;
    for(ll i=1;i<=n;i++)
    {
        cin>>t[i]>>c[i];  p[i]=i;
        t[i]+=t[i-1];  c[i]+=c[i-1];  k[i]=t[i]+s;
    }
    for(ll i=1;i<=n;i++)  f[i]=t[i]*c[i]+s*c[n];
    sort(p+1,p+1+n,cmpk);  cdq(1,n);
    cout<<f[n]<<endl;
    return 0;
}