任务安排2

题目链接：https://www.acwing.com/problem/content/303/

思路：在任务安排1中已经推出dp[i]=dp[j]-(m+sumt[i])*sumc[j]+sumt[i]*sumc[i]+m*sumc[n]

可以假设在求dp[i]时，dp[i]由dp[j]转换而来比由dp[k]转换来更优，（j>k）。

那dp[j]-(m+sumt[i])*sumc[j]+sumt[i]*sumc[i]+m*sumc[n]<=dp[k]-(m+sumt[k])*sumc[k]+sumt[k]*sumc[k]+m*sumc[n]

化简得(dp[j]-dp[k])/(sumc[j]-sumc[k])<=m+sumt[i]

如果上试成立的话，那j点就比k点更优，可以把k点淘汰掉。

令g[k,j]=(dp[j]-dp[k])/(sumc[j]-sumc[k])

如果对于k<j<i，g[k,j]>g[j,i] 那么 j 也是可以淘汰的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[500005],sumt[500005],sumc[500005],q[500005];
bool fun(int x,int y,int i,int m)
{
    if( dp[x]-dp[y]<=(m+sumt[i])*(sumc[x]-sumc[y]) )
        return true;
    return false;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x,y;
        cin>>x>>y;
        sumt[i]=sumt[i-1]+x;
        sumc[i]=sumc[i-1]+y;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    int head=0,tail=1;
    q[0]=0;
    for(int i=1; i<=n; i++)
    {
        while((head+1<tail)&&fun(q[head+1],q[head],i,m))
            head++;
        int x=q[head];
        dp[i]=dp[x]-(m+sumt[i])*sumc[x]+sumt[i]*sumc[i]+m*sumc[n];
        while((head+1<tail)&&(dp[q[tail-1]]-dp[q[tail-2]])*(sumc[i]-sumc[q[tail-1]])>=(dp[i]-dp[q[tail-1]])*(sumc[q[tail-1]]-sumc[q[tail-2]]) )
            tail--;
        q[tail++]=i;
    }
    cout<<dp[n]<<endl;
}