【日常小测】巡游计划

题目大意

有$n(n \le 52501)$个城市,依次分布在数轴上
若你到达$i$号城市,则你必须停留$a_i$个单位时间
若你当前在$i$号城市,则你只能前往编号$\in (i,i+k]$的城市
若你在城市$i$,打算前往城市$j$,那么你会花费$|p_i-p_j| \cdot b_i$的时间
现在你从$1$号城市出发,最终到达$n$号城市,问花费的最短时间

解题报告

下面内容建立在你已经会了BZOJ 1492的维护凸壳的做法

先不考虑那个绝对值的限制,显然就是一个斜率DP的形式
我们考虑对序列建一个线段树,每一次得到了$i$号城市的答案后
我们在线段树上进行依次区间加的操作,即将$i$号城市对应的点加入线段树对应结点的凸壳内
因为在线段树上只会被拆分成$O(\log n)$个结点、插入凸壳复杂度$O(\log n)$,于是复杂度为$O(n \log^2 n)$

至于如何查询?我们从左到右依次处理,假设我们当前想得到$i$号城市的答案
那我们在$i$在线段树内对应的节点到根的路径上的每一个凸壳我们都询问一次答案
然后取一个最值就可以了,时间复杂度仍然是$O(n \log^2 n)$的

现在我们考虑绝对值的限制
我们可以钦定$p_i$与$p_j$的大小关系
具体来说,我们在得到$i$号城市的答案后,我们只是将他扔到线段树上去,但先不建立凸包
然后我们对那棵线段树进行中序遍历,那么在走到结点i的时候,我们已经知道了需要查询哪些点,凸壳总共有哪些点
于是我们将这些东西扔到一起,然后排序,然后从小到大遍历一次

如果是查询的点,就到当前的凸壳中更新答案
如果是应该加入到凸壳的点,那就加入到凸壳中
因为已经排过序,所以绝对值可以打开

我们再从大到小再来一遍,这样就可以得到这个结点的所有答案了
不难发现一个点只会被插入凸壳$O(\log n)$次,也只会被查询这么多次
所以时间复杂度仍然为$O(n \log^2 n)$

【BZOJ 4518】[Sdoi2016] 征途

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4518
数据生成器:http://paste.ubuntu.com/23249800/

做过玩具装箱的童鞋,看一眼就知道是斜率DP吧?

#include<bits/stdc++.h>
#define pow(x) ((x)*(x))
#define LL long long
using namespace std;

const int N = 3000+9;
const LL INF = 1e16;

LL f[N][N];
short n,m,l[N],sum,que[N][N],t1[N],t2[N];
double slope[N][N],Y[N][N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){ 
	n = read(); m = read();
	for (int i=1;i<=n;i++) sum += (l[i] = read()), l[i] += l[i-1];
	for (int i=0;i<m;i++) t1[i] = 1, f[n][i] = -1; t2[0] = 1;
	for (int i=1;i<=n;i++) for (int j=m-1;~j;j--) {
		if (t1[j]>t2[j]) continue; double tmp = 2.0*m*((double)m*l[i]-sum);
		while (t2[j] > t1[j] && slope[j][t1[j]] <= tmp) t1[j]++; 
		f[i][j+1] = f[que[j][t1[j]]][j] + pow(sum-(LL)m*(l[i]-l[que[j][t1[j]]]));
		tmp = f[i][j+1] + pow((double)m*l[i]); 
		while (t1[j+1] < t2[j+1] && ((tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]) <= slope[j+1][t2[j+1]-1])) t2[j+1]--;
		if (t1[j+1] <= t2[j+1]) slope[j+1][t2[j+1]] = (tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]); 
		t2[j+1]++; que[j+1][t2[j+1]] = i; Y[j+1][t2[j+1]] = tmp; 		
	} LL vout = INF;
	for (int i=1;i<=m;i++) if (~f[n][i]) vout = min(vout,f[n][i]+(LL)(m-i)*pow(sum));
	printf("%lld\n",vout/m); return 0;
}

然而再zgs的OJ上莫名其妙RE了两个点?
奥妙重重……..

【NOI六连测】[D4T1] 数学

题目传送门:http://pan.baidu.com/s/1eRRG6Wy
离线版题目:http://paste.ubuntu.com/18459243/
数据传送门:http://pan.baidu.com/s/1miarNuS

这一道题目,真的是十分可惜。考试前一个小时,码完了O(K*n^2) 的暴力DP,但一直到考试结束前9分钟才推出斜率DP的式子。
本来以为斜率DP可以随便切了QAQ,现在来看,代码实现确实不恼火了,但是推式子还是很恼火啊!
这一道题目,式子推出来之后,也就没什么好说的了。先贴一贴斜率DP的代码,后续再来更决策单调,和神奇的二分的代码。

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int K = 50+9;

double x[K][MAXN/2],y[K][MAXN/2],rev[MAXN],ret,arr[MAXN];
int AA[MAXN],n,k,l[K],r[K],pos[K][MAXN/2]; 

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

#define slope(t,b,a) (y[t][a]-y[t][b])/(x[t][a]-x[t][b])

inline void update(int t, double X, double Y, int i){
	int tmp = r[t]+1; x[t][tmp]=X; y[t][tmp]=Y;
	while (l[t] < r[t]) if (slope(t,r[t],tmp) > slope(t,r[t]-1,r[t])) r[t]--;
		else break;
	x[t][++r[t]] = X; y[t][r[t]] = Y; pos[t][r[t]] = i;
}

inline double Get(int t, int w){
	while (l[t] < r[t]) if (slope(t,l[t],l[t]+1) > rev[w+1]) l[t]++;
		else break;
	return (arr[w]-arr[pos[t][l[t]]])*rev[w+1]+y[t][l[t]];
}

int main(){
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	n = read(); k = read()-1;
	for (int i=1;i<=n;i++) AA[i] = read();
	for (int i=1;i<=n;i++) arr[i] = (double)AA[i]+arr[i-1];
	for (int i=n;i;i--) rev[i] = rev[i+1] + (double)1/AA[i]; 
	for (int i=1;i<=n;i++) ret += (double)AA[i]*rev[i];
	for (int i=0;i<=k;i++) l[i] = 1;
	
	for (int w=1;w<n;w++){
		for (int i=1;i<k;i++) if (r[i]) 
			update(i+1,arr[w],Get(i,w),w);
		update(1,arr[w],arr[w]*rev[w+1],w);
	} 
	double vout = 0;
	for (int i=l[k];i<=r[k];i++)
		vout = max(vout, y[k][i]);
	printf("%.15lf\n",ret - vout);
	return 0;
}