蒟蒻真是什么都不会！

久仰CDQ分治大名QAQ

感觉后面的小哥cool是个CDQ分治大师

结果拖到现在才好好地学习一番TAT

蒟蒻太差只写了三道不要喷啊啊啊啊

感觉理解得并不好TAT

BZOJ：

BZOJ-1492: [NOI2007]货币兑换Cash

应该是最经典的CDQ分治了吧

从《Cash》谈一类分治算法的应用

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const int NN = 100005;
int n,top,stk[NN];
double f[NN];
struct P
{
	double x,y,a,b,k,rate;
	int num;
}p[NN],t[NN];
double Get_k(int xx,int yy)
{
	if (!yy) return -1e20;
	if (fabs(p[xx].x-p[yy].x) < eps) return 1e20;
	return (p[yy].y-p[xx].y) / (p[yy].x-p[xx].x);
}
bool cmp(P xx,P yy) { return xx.k > yy.k; }

void Solve(int l,int r)
{
	if (l == r)
	{
		f[l] = max(f[l],f[l-1]);
		p[l].y = f[l]/(p[l].a*p[l].rate + p[l].b);
		p[l].x = p[l].rate * p[l].y;
		return;
	}
	int mid = (l+r) >> 1, l1 = l, l2 = mid+1, j = 1;
	for (int i=l;i<=r;++i)
		if (p[i].num <= mid) t[l1++] = p[i];
		else t[l2++] = p[i];
	for (int i=l;i<=r;++i) p[i] = t[i];
	Solve(l,mid);
	top = 0;
	for (int i=l;i<=mid;++i)
	{
		while (top > 1 && Get_k(stk[top-1],stk[top]) < Get_k(stk[top-1],i)+eps) --top;
		stk[++top] = i;
	}
	stk[++top] = 0;
	for (int i=mid+1;i<=r;++i)
	{
		while (j < top && Get_k(stk[j],stk[j+1]) + eps > p[i].k) ++j;
		f[p[i].num] = max(f[p[i].num],p[stk[j]].x*p[i].a+p[stk[j]].y*p[i].b);
	}
	Solve(mid+1,r);
	l1 = l, l2 = mid+1;
	for (int i=l;i<=r;++i)
		if (((p[l1].x < p[l2].x || (fabs(p[l1].x-p[l2].x) < eps && p[l1].y < p[l2].y)) || l2 > r) && l1 <= mid)
			t[i] = p[l1++];
		else t[i] = p[l2++];
	for (int i=l;i<=r;++i) p[i] = t[i];
}


int main()
{
	scanf("%d%lf",&n,&f[0]);
	for (int i=1;i<=n;++i)
	{
		scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate);
		p[i].k = -p[i].a / p[i].b;
		p[i].num = i;
	}
	sort(p+1,p+1+n,cmp);
	Solve(1,n);
	printf("%.3lf\n",f[n]);
	return 0;
} 

不要问我为什么后面两道的代码也是一个格式的

BZOJ-2726: [SDOI2012]任务安排

设$f[i]$为将前$i$个任务划分完成的最小费用，$T[i],F[i]$分别表示$t$和$f$的前缀和，则不难写出转移方程式：

$$f[i]=min\{ f[j]+(F[n]-F[j])\times(T[i]-T[j]+S) \},(1<=j<=i-1)$$

令$p[i].x=F[i],p[i].y=f[j]-F[n]\times T[j]+F[j]\times T[j]-S\times F[j],p[i].k=T[i]$则有：

$$f[i]=min\{ -p[i].k \times p[j].x + p[j].y\}$$

出题人太强了打得蒟蒻只能用CDQ惹

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const int NN = 500005;
int F[NN],T[NN],st[NN],n,S,top;
LL f[NN];
struct P
{
	LL x,y,k;
	int num;
}q[NN],t[NN];
bool cmp(P xx,P yy)
{
	return xx.k < yy.k;
}
inline LL U(int j,int k) { return (LL)q[k].y-q[j].y;}
inline LL D(int j,int k) { return (LL)q[k].x-q[j].x;}
inline bool Check(const P&a,const P& b)
{
	return a.x<b.x || a.x==b.x&&a.y<b.y;
}
void Solve(int l,int r)
{
	if (l == r)
	{
		q[l].x = (LL) F[l];
		q[l].y = (LL) f[l] - (LL)F[n]*T[l] + (LL)F[l]*T[l] - (LL)S*F[l];
		return;
	}
	int mid = (l+r) >> 1, l1 = l, l2 = mid+1,j = 1;
	for (int i=l;i<=r;++i)
		if (q[i].num > mid) t[l2++] = q[i]; else t[l1++] = q[i];
	for (int i=l;i<=r;++i) q[i] = t[i];
	Solve(l,mid);
	top = 0;
	for (int i=l;i<=mid;++i)
	{
		while (top>1 && (LL)U(st[top-1],st[top])*D(st[top-1],i)>(LL)U(st[top-1],i)*D(st[top-1],st[top]))
			top--;
		st[++top] = i;
	}
	for (int i=mid+1;i<=r;++i)
	{
		while (j<top && U(st[j],st[j+1]) < (LL)q[i].k*D(st[j],st[j+1])) ++j;
		f[q[i].num] = min(f[q[i].num],-(LL)q[i].k*q[st[j]].x+q[st[j]].y+(LL)F[n]*(T[q[i].num]+S));
	}
	Solve(mid+1,r);
	l1 = l, l2 = mid+1;
	for (int i=l;i<=r;++i)
	{
		if ((l2 > r || Check(q[l1],q[l2])) && l1<=mid) t[i] = q[l1++]; else t[i] = q[l2++];
	}
	for (int i=l;i<=r;++i) q[i] = t[i];
}

int main()
{
	scanf("%d%d",&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];
	for (int i=1;i<=n;++i) q[i].num = i, q[i].k = T[i], f[i] = INF;
	sort(q+1,q+1+n,cmp);
	Solve(0,n);
	printf("%lld\n",f[n]);
	return 0;
}

BZOJ-3461: Jry的时间表

$f[i]$表示$[1,i]$操作一次，且在$[j+1,i]$处操作

分把$[j+1,i]$改为$b[i]$或改为$b[j]$

其实把数列倒一下就可以了

$$f[i] = max\{ sum[j] + b[i] \times (i-j) \} = b[i] \times i + max\{ -j \times b[i] + sum[j]\} (0<= j < i)$$

上CDQ分治优化即可，最后：

$$ans = max\{ fl[i]-sum[i]+fr[j]+sum[j-1] \}(0 <= i < j <= n)$$

拆开来然后维护前缀最大的$fl[i]-sum[i]$就可以辣

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NN = 500010;
const double eps = 1e-9;
int n,a[NN],b[NN],stk[NN],top;
LL sum[NN],f[NN],fl[NN],fr[NN],pre,ans;
struct P
{
	int x,num; LL y;
}p[NN],t[NN];
inline double Get_k(int x,int y)
{
	return (double)(p[x].y-p[y].y)/(double)(p[x].x-p[y].x);
}
inline bool cmp(P xx,P yy)
{
	if (xx.x == yy.x) return xx.y > yy.y; 
	else return xx.x < yy.x;
}
inline double Pos(int x,int y) { return (double)(sum[x]-sum[y])/(double)(x-y); }
inline LL ASK(int x)
{
	int l=1,r=top-1,tmp=top,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
 	   if ((double)x>Pos(stk[mid],stk[mid+1])) r=(tmp=mid)-1; else l=mid+1;
	}
	return sum[stk[tmp]]-(LL)stk[tmp]*x;
}
void Solve(int l,int r)
{
	if (l == r)
	{
		p[l].x = b[l+1];
		p[l].y = sum[l]-(LL)b[l+1]*l;
		return;
	}
	int mid = (l+r) >> 1, l1 = l, l2 = mid+1, j = 1;
	for (int i=l;i<=r;++i)
		if (p[i].num <= mid) t[l1++] = p[i];
		else t[l2++] = p[i];
	for (int i=l;i<=r;++i) p[i] = t[i];
	Solve(l,mid);
	top = 0;
	for (int i=l;i<=mid;++i)
	{
		while (top > 1 && Get_k(stk[top-1],stk[top]) <= Get_k(stk[top-1],i)+eps) --top;
		stk[++top] = i;
	}
	for (int i=mid+1;i<=r;++i)
	{
		while (j<top && (p[stk[j]].y-p[stk[j+1]].y) <= ((LL)p[i].num*(p[stk[j+1]].x-p[stk[j]].x))) ++ j;
		f[p[i].num] = max(f[p[i].num],(LL)p[stk[j]].x*p[i].num+p[stk[j]].y);
	}
	Solve(mid+1,r);
	l1 = l, l2 = mid+1;
	for (int i=l;i<=r;++i)
		if (((p[l1].x < p[l2].x || (fabs(p[l1].x-p[l2].x) < eps && p[l1].y < p[l2].y)) || l2 > r) && l1 <= mid)
			t[i] = p[l1++];
		else t[i] = p[l2++];
	for (int i=l;i<=r;++i) p[i] = t[i];
}
void Work()
{
	for (int i=1;i<=n;++i) sum[i] = sum[i-1] + a[i], p[i].num = i;
	top = 0;
	for (int i=0;i<=n;stk[++top] = i++)
	{
		if (i)
			f[i] = (LL)b[i]*i+ASK(b[i]);
		while (top > 1 && Pos(i,stk[top]) > Pos(stk[top],stk[top-1])) --top;
	}
	sort(p+1,p+1+n,cmp);
	Solve(0,n);	
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i) scanf("%d",&b[i]);
	Work();
	for (int i=1;i<=n;++i) fl[i] = f[i];
	for (int i=1,j=n;i<j;++i,--j) swap(a[i],a[j]), swap(b[i],b[j]);
	Work();
	for (int i=1;i<=n;++i) fr[n-i+1] = f[i];
	for (int i=1;i<=n;++i) sum[i] = sum[i-1] + a[n-i+1];
	ans = sum[n];
	for (int i=1;i<=n;++i) ans = max(fr[i]+sum[i-1]+pre,ans), pre = max(pre,fl[i]-sum[i]);
	printf("%lld\n",ans);
	return 0;
}

不知道为什么A掉这道题成就感这么强WAW