题解：P5785

wangyizhi · 2025-02-06 21:23:28 · 题解

题目传送门

貌似现有的题解中没有我这种神奇的做法？

也许是不大符合正常斜率优化的写法。

题意分析

以下记原题中 c 的前缀和为 C，t 的前缀和为 T。

首先，如果你做过这题的弱化版P2365 任务安排，就可以列出一个 O(n^2) 的状态转移方程：

将其中的柿子写成关于 T_i 的直线方程：

然后问题就转化成了求一堆直线在一点处的最小值。

那么我们只需要维护能取到最小值的直线就行了，然后再根据交点二分求出这一点在哪条直线上进而求出结果。

如果你做过P3194 水平可见直线的话，就应该会这个做法了。先将直线按斜率排序，然后一个个加进去。由于 F_n-F_j 是递减的，所以这里就不需要排序了，一边维护直线一边 DP 就行了。

于是这题就做完了。

AC Code

// by wangyizhi(571247)
#include<iostream>
using namespace std;
using ll=long long;
using ld=long double;
#define int ll
using pii=pair<int,int>;
const int N=3e5+1;
int t[N],f[N],dp[N],st[N],top=0;
struct line
{
    int k,b;
    inline int get(int x){return k*x+b;}
}l[N];
inline ld inter(line x,line y){return (ld)(y.b-x.b)/(x.k-y.k);}
signed main()
{
    int n,s;
    cin>>n>>s;
    for(int i=1;i<=n;i++) cin>>t[i]>>f[i],t[i]+=t[i-1],f[i]+=f[i-1];
    l[0]={f[n]-f[0],(s-t[0])*(f[n]-f[0])};
    for(int i=1;i<=n;i++)
    {
        if(!top) dp[i]=l[st[top]].get(t[i]);
        else if(t[i]>=inter(l[st[top]],l[st[top-1]])) dp[i]=l[st[top]].get(t[i]);
        else
        {
            int le=0,ri=top-1,mid,res=0;
            while(le<=ri)
            {
                mid=(le+ri)/2;
                if(inter(l[st[mid]],l[st[mid+1]])>=t[i]) res=mid,ri=mid-1;
                else le=mid+1;
            }
            dp[i]=l[st[res]].get(t[i]);
        }
        l[i]=line{f[n]-f[i],dp[i]+(s-t[i])*(f[n]-f[i])};
        if(!top) st[++top]=i;
        else // top>=1
        {
            while(top&&(
                (l[i].k<l[st[top]].k&&inter(l[i],l[st[top]])<=inter(l[st[top]],l[st[top-1]]))
                ||(l[i].k==l[st[top]].k&&l[i].b<l[st[top]].b)
            )) top--;
            if(!top||inter(l[i],l[st[top]])>inter(l[st[top]],l[st[top-1]])) st[++top]=i;
        }
    cout<<dp[n]<<"\n";
    return 0;
}