Loading...

斜率优化 学习笔记

check评论:0 条 remove_red_eye浏览量:55 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-11

先抓一道板子

任务安排

题意:给定$n$个任务,每个任务花费时间$t$,单位时间消耗$c$元,将他们分成若干组,每一组的花费是这一组所有任务的结束时间乘所有任务的价值和再加上一个常数$s$,求最小代价

显然可以写出$dp$方程$dp[i][j]=min(dp[i][j],dp[k][j-1]+(sum[i]-sum[k])(t[i]+j*s))$

其中$sum[i]$表示前$i$个任务花费和,$t[i]$表示前$i$个任务时间和,$dp[i][j]$表示前$i$个任务分成$j$组最小代价

显然这是$n^3$的,啥都过不了,考虑优化

如果把$dp$简化成一维的会有个问题,我们不知道他分了多少组,没法算贡献

考虑转移的时候直接加上当前分组对后面所有答案的贡献,这样的话$dp[i]$就代表了前$i$个任务分组个数对全局的贡献加上前面的任务的花费

$dp[i]=min(dp[k]+(sum[i]-sum[k])*t[i]+(sum[n]-sum[k])*s)$

这个可以$O(n^2)$计算了

但是如果这题$n$在$1e5$级别,就过不了了,考虑优化

我们令$j<k<i$,且$i$从$j$转移比从$k$转移更好

那么$dp[k]+(sum[i]-sum[k])*t[i]+(sum[n]-sum[k])*s>=dp[j]+(sum[i]-sum[j])*t[i]+(sum[n]-sum[j])*s$

化简得到$dp[k]-dp[j]>(t[i]+s)*(sum[k]-sum[j])$

即$\frac{dp[k]-dp[j]}{sum[k]-sum[j]}>t[i]+s$

这玩意好像斜率QAQ,意思是对于每个$i$,只要满足了这个式子的两个点$j,k$,一定是从$j$转移更优

然后就很简单了(

#include <bits/stdc++.h>
using namespace std;
int n,t[5010],f[5010],s,dp[5010],st[5010];
int main()
{
    memset(dp,0x3f,sizeof(dp));
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&t[i],&f[i]);
        t[i]+=t[i-1],f[i]+=f[i-1];
    }
    dp[0]=0;
    int l=1,r=0;
    st[++r]=0;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&(dp[st[l]]-dp[st[l+1]])>(f[st[l]]-f[st[l+1]])*(t[i]+s))
        {
            ++l;
        }
        dp[i]=dp[st[l]]+t[i]*(f[i]-f[st[l]])+(f[n]-f[st[l]])*s;
        while(l<r&&(dp[st[r]]-dp[st[r-1]])*(f[i]-f[st[r]])>=(dp[i]-dp[st[r]])*(f[st[r]]-f[st[r-1]]))
        {
            r--;
        }
        st[++r]=i;
    }
    cout<<dp[n];
}

仓库建设

题意:自己看吧(

令$c[i]$表示在$i$建设仓库的花费,$Q[i]$表示前$i$个仓库的货物总和,$sum[i]$表示前$i$个仓库的货物都运送到$i$的花费

显然$dp[i]=min(dp[k]+c[i]+(sum[i]-sum[k])-(dis[i]-dis[k])*Q[k])$

令$A[i]=sum[i]-Q[i]*dis[i]$,$B[i]=dp[i]-A[i]$

用上道题的方法,写成斜率的形式,即$\frac{B[j]-B[k]}{Q[j]-Q[k]} < dis[i]$

然后就完了

#include <bits/stdc++.h>
using namespace std;
#define int long long
int dis[1000010],c[1000010],Q[1000010],dp[1000010],sum[1000010];
int n,A[1000010],B[1000010],st[1000010],l,r;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&dis[i],&Q[i],&c[i]);
        Q[i]+=Q[i-1];
        sum[i]=sum[i-1]+Q[i-1]*(dis[i]-dis[i-1]);
        A[i]=sum[i]-Q[i]*dis[i];
    }
    l=r=0;
    st[0]=0;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&(B[st[l+1]]-B[st[l]])<dis[i]*(Q[st[l+1]]-Q[st[l]]))
        {
            ++l;
        }
        dp[i]=dp[st[l]]+c[i]+(sum[i]-sum[st[l]])-Q[st[l]]*(dis[i]-dis[st[l]]);
        B[i]=dp[i]-A[i];
        while(l<r&&(B[st[r]]-B[st[r-1]])*(Q[i]-Q[st[r]])>=(B[i]-B[st[r]])*(Q[st[r]]-Q[st[r-1]]))
        {
            --r;
        }
        st[++r]=i;
    }
    cout<<dp[n];
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名