首页 > 代码库 > 洛谷P2365 任务安排 [解法二 斜率优化]
洛谷P2365 任务安排 [解法二 斜率优化]
解法一：http://www.cnblogs.com/SilverNebula/p/5926253.html
解法二：斜率优化
在解法一中有这样的方程：dp[i]=min(dp[i],dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j]) )
其中min的后半部分，也就是dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j]) 计算了将j~i分为一组的花费（以及提前计算的受影响花费）
设f(j)=dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j])，i不变时，若 f(j1)<f(j2) ，显然从j1到i分为一组比j2到i分为一组的答案更优，而如果j1<j2，显然j2可以被舍弃掉。由以上两个限制条件很容易联想到单调队列，进而想到斜率优化（并不）。
现在来考虑 j1<j2 ,f(j1)<f(j2) 的情况。把f()展开写再化简，可以得到(dp[j1]-dp[j2])/(sumf[j1]-sumf[j2])<=sumt[i]+s (sumf和sumt分别是f、t的前缀和）
利用这个式子列斜率方程，维护一个下凸壳即可←然而并不能理解
我的想法：(dp[j1]-dp[j2])/(sumf[j1]-sumf[j2])显然是越小越好，我们可以据此维护斜率单调队列的队尾(具体看代码)，而上面那个式子用来维护队头，即可行：
斜率优化10ms，O（n^2）算法43ms
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<cstring> 7 using namespace std; 8 const int mxn=6000; 9 int n;10 int s;11 int t[mxn],f[mxn];12 int sumt[mxn],sumf[mxn];13 int dp[mxn];14 int q[mxn];15 int gup(int j,int k){16 return (dp[j]-dp[k]);17 }18 int gdown(int j,int k){19 return sumf[j]-sumf[k];20 }21 int gdp(int i,int j){22 return dp[j]+(sumf[i]-sumf[j])*sumt[i]+s*(sumf[n]-sumf[j]);23 }24 int main(){25 scanf("%d%d",&n,&s);26 int i,j;27 for(i=1;i<=n;i++){28 scanf("%d%d",&t[i],&f[i]);29 sumt[i]=sumt[i-1]+t[i];30 sumf[i]=sumf[i-1]+f[i];31 }32 memset(dp,0x3f,sizeof dp);33 dp[0]=0;34 int hd=0,tl=0;35 q[hd]=0;36 for(i=1;i<=n;i++){37 while(hd<tl && gup(q[hd],q[hd+1])>=(sumt[i]+s)*gdown(q[hd],q[hd+1]) )38 hd++;39 dp[i]=gdp(i,q[hd]);40 while(hd<tl && gup(i,q[tl])*gdown(q[tl],q[tl-1])<=gup(q[tl],q[tl-1])*gdown(i,q[tl]) )tl--;41 q[++tl]=i;42 }43 printf("%d",dp[n]);44 return 0;45 }
洛谷P2365 任务安排 [解法二 斜率优化]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。