本文共 1975 字，大约阅读时间需要 6 分钟。

$普通n^2的转移是$

$设f是费用系数的前缀和数组,t是任务花费时间的前缀和数组$

$$dp[i]=dp[j]+s\ast (f[n]-f[j])+t[i]\ast (f[i]-f[j])$$

$让我们按照惯例化简一下$

$$dp[j]=s\ast f[j]+t[i]\ast f[j]-s\ast f[n]-t[i]\ast f[i]+dp[i]$$

$$dp[j]=(s+t[i])\ast f[j]-s\ast f[n]-t[i]\ast f[i]+dp[i]$$

$这样把dp[j]看成y,把f[j]看成x$

$发现直线的斜率确定,是s+t[i],是个定值(因为当前在转移i)$

$发现直线的截距是-s\ast f[n]-t[i]\ast f[i]+dp[i]$

$惊人的发现!!截距只和i有关,说明截距越小,dp[i]越小$

现在的任务就是找到一个j,使得这条直线的截距最小

$那么维护一个下凸包,相邻两点的斜率递增$

$第一个斜率大于s+t[i]的j就是最优的j$

#include 
   
    using namespace std;const int maxn=5009;int n,s,tt[maxn],ff[maxn],q[maxn],dp[maxn];int t[maxn],f[maxn];int l=1,r=1;int mu(int l,int r){ return dp[l]-dp[r];}int zi(int l,int r){ return f[l]-f[r]; }int main(){	cin >> n >> s;	memset(dp,127,sizeof(dp));	dp[0]=0;	for(int i=1;i<=n;i++)	cin >> tt[i] >> ff[i],t[i]=t[i-1]+tt[i];	for(int i=1;i<=n;i++)	f[i]=f[i-1]+ff[i];	for(int i=1;i<=n;i++)	{		while( l
    
     <=zi(q[l+1],q[l])*( s+t[i] ) )	l++;		dp[i]=dp[q[l]]-( s+t[i] )*f[q[l]]+s*f[n]+t[i]*f[i];		while( l
     
      <=mu(q[r],q[r-1])*zi(i,q[r]) )			r--;//剔除斜率小于当前直线的点 		q[++r]=i;	}	cout << dp[n];}
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/108210847 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！