bzoj2726 洛谷P2365 [SDOI2012]任务安排 cdq分治+斜率优化

本文主要是介绍bzoj2726 洛谷P2365 [SDOI2012]任务安排 cdq分治+斜率优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：
bzoj2726
洛谷2365

洛咕上好像 $O(n^2)$ 能过……还没有负数的情况……
如果没有负数，就直接大莉上斜率优化就珂以了qwq
转移方程是 $d p [i] = d p [j] + s u m T [i] * (c [i] - c [j]) + S * (c [n] - c [j])$ （ $s u m T, c$ 表示前缀和）
这里放上洛咕AC，bzojWA的代码：

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<vector>
#define re register int
#define rl register ll
using namespace std;
typedef long long ll;
ll read() {rl x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')	f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
namespace I_Love {const int Size=50005;
const int LOG=20;
int n,s,T[Size],F[Size],Queue[Size];
int sumt[Size],c[Size],dp[Size];
inline double X(int i) {return c[i];
}
inline double Y(int i) {return dp[i];
}
inline double slope(int i,int j) {return (Y(j)-Y(i))/(X(j)-X(i));
}
void Fujibayashi_Ryou() {n=read();s=read();for(re i=1; i<=n; i++) {T[i]=read();F[i]=read();sumt[i]=sumt[i-1]+T[i];c[i]=c[i-1]+F[i];}int hd=1,tl=1;Queue[tl]=0;for(re i=1; i<=n; i++) {while(hd<tl && slope(Queue[hd],Queue[hd+1])<=sumt[i]+s)	hd++;dp[i]=dp[Queue[hd]]+sumt[i]*(c[i]-c[Queue[hd]])+s*(c[n]-c[Queue[hd]]);while(hd<tl && slope(Queue[tl-1],Queue[tl])>=slope(Queue[tl],i))	tl--;Queue[++tl]=i;}printf("%d",dp[n]);
}}
int main() {I_Love::Fujibayashi_Ryou();return 0;
}

然后考虑 $T, F$ 珂能为负的情况。
$T$ 和 $F$ 珂能为负会导致 $T, F$ 的前缀和不单调。
对于这种不单调的情况珂以套一个 $c d q$ 分治：
$c d q$ 分治的本质是求解左右区间，然后用左区间推右区间。
首先把求解第 $i$ 个 $d p$ 值看作一个操作。
要解决 $T$ 的前缀和不单调的情况，就把 $T$ 作为 $c d q$ 分治的第一维，先按照 $T$ 的前缀和排序。
排序后就珂以保证 $T$ 前缀和有序，考虑怎样从左边推到右边：
若 $l = r$ ，说明当前区间只有一个操作了。对这个操作建点即可qwq。
对于当前分治到的区间 $[l, r]$ ，把原编号 $< = m i d$ 的放到 $[l, m i d]$ 内，否则放到 $[m i d + 1, r]$ 内，然后先求解 $[l, m i d]$ 。
此时 $[l, m i d]$ 区间的原编号都比 $[m i d + 1, r]$ 的原编号要小，而 $T$ 的前缀和也是单调的，所以就珂以大莉斜率优化了qwq。
注意要先左区间推右区间，再递归求解右区间。否则 $l = r$ 的时候这个位置的 $d p$ 值还没求出来，就很臭qwq。

毒瘤代码

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
#define rl register ll
using namespace std;
typedef long long ll;
ll read() {rl x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')    f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
const int Size=500005;
const int INF=0x3f3f3f3f;
ll n,S,F[Size],T[Size],dp[Size];
struct node {double x,y; int id;
} w[Size],tmp[Size];
inline bool comp(node mhy,node zwt) {return T[mhy.id]<T[zwt.id];
}
inline bool operator < (node mhy,node zwt) {if(mhy.x!=zwt.x)    return mhy.x<zwt.x;return mhy.y<zwt.y;
}
void Divide(int l,int r) {//divide [l,r] into [l,mid] & [mid+1,r]//id<=mid  ->  [l,mid]//id>mid   ->  [mid+1,r]int mid=(l+r)>>1;int ptr1=l,ptr2=mid+1;for(re i=l; i<=r; i++) {if(w[i].id<=mid) {tmp[ptr1++]=w[i];} else {tmp[ptr2++]=w[i];}}for(re i=l; i<=r; i++) {w[i]=tmp[i];}
}
node Queue[Size];
inline double slope(node A,node B) {return (B.y-A.y)/(B.x-A.x);
}
void CDQ_Divide(int l,int r) {if(l==r) {//l=r就建点 w[l].x=F[w[l].id];w[l].y=dp[w[l].id];return;}int mid=(l+r)>>1;//把这个区间按照原编号id分成[l,mid]和[mid+1,r] //分的过程不会影响T的前缀和的单调性qwq Divide(l,r);CDQ_Divide(l,mid);//斜率优化，要先左推右，再递归求解右边 int hd=1,tl=0;for(re i=l; i<=mid; i++) {while(hd<tl && slope(Queue[tl-1],Queue[tl])>slope(Queue[tl-1],w[i]))    tl--;Queue[++tl]=w[i];}for(re i=mid+1; i<=r; i++) {while(hd<tl && slope(Queue[hd],Queue[hd+1])<S+T[w[i].id])    hd++;int j=Queue[hd].id;dp[w[i].id]=min(dp[w[i].id],dp[j]+S*(F[n]-F[j])+T[w[i].id]*(F[w[i].id]-F[j]));}CDQ_Divide(mid+1,r);
}
int main() {
//  freopen("data.txt","r",stdin);
//  freopen("WA.txt","w",stdout);memset(dp,0x3f,sizeof(dp));n=read();S=read();for(re i=1; i<=n; i++) {//T,F表示前缀和 T[i]=T[i-1]+read();F[i]=F[i-1]+read();w[i].id=i;}sort(w+1,w+1+n,comp);//这个初始化很孙 dp[0]=0;CDQ_Divide(0,n);printf("%lld",dp[n]);return 0;
}