jzoj 4017. 【雅礼联考DAY01】逃跑 (Standard IO)

Description

Konrad， Delfador 和 Kalenz 一行人又喜闻乐见地被追杀了。
他们面临的是一条有 N 个地点的路， 他们从 0 号地点出发， 要逃到 N 号地点去。每个地点的战斗都有一定的金币收入 Ai，也有一定的部队损失 Bi。
为了更好地逃生， Delfador 还弄到了一块传送宝石，这样一行人就能向后传送不超过 L 的距离。从一个地点传送到另一个地点时，Konrad 会选择路径上除起点外的地形指数 Ci 最大的地点进行战斗，地形指数相同时选择最靠后的。
作为优秀的领导者， Konrad 希望总金币收入与总部队损失的比值最大。

Input

第一行，两个整数 N, L。
接下来 N 行，每行两个整数，分别表示 Ai, Bi, Ci。

Output

一行，一个实数，表示答案。
答案请使用科学计数法输出，保留 9 位小数，具体参见输出样例。指数为 0 时，最后应当输出’0.000000000e+000’。

Sample Input

5 3
1 1 1
1 2 2
2 3 1
1 9 2
1 1 1

Sample Output

3.750000000e-001

Data Constraint

Solution

这是分数规划的形式，
我们设最大比值为$q$q，那么显然一定有$q=\frac{\sum_{i=1}^ka_{p_i}}{\sum_{i=1}^kb_{p_i}}$q=∑i=1k​bpi​​∑i=1k​api​​​，其中$\{p_k\}${pk​}为选择点的集合
我们把上面的式子移项，得：
$q\cdot\sum_{i=1}^kb_{p_i}=\sum_{i=1}^ka_{p_i}$q⋅i=1∑k​bpi​​=i=1∑k​api​​
$\sum_{i=1}^ka_{p_i}-q\cdot\sum_{i=1}^kb_{p_i}=0$i=1∑k​api​​−q⋅i=1∑k​bpi​​=0
若是$\sum_{i=1}^ka_{p_i}-q\cdot\sum_{i=1}^kb_{p_i}<0$∑i=1k​api​​−q⋅∑i=1k​bpi​​<0，说明$q$q大了
若是$\sum_{i=1}^ka_{p_i}-q\cdot\sum_{i=1}^kb_{p_i}>0$∑i=1k​api​​−q⋅∑i=1k​bpi​​>0，说明$q$q小了
这样就可以二分了，每次二分一个答案$mid$mid，令$d_i=a_i-b_i\cdot mid$di​=ai​−bi​⋅mid，我们就把每个点的贡献转换成了$d_i$di​，我们要让战斗的点的$d_i$di​的和最大，这样才能尽量使最终的答案最大
设$f_i$fi​为到达第$i$i个点，中途战斗点的$d_i$di​的和的最大值，易得转移方程：
$f_i=\max\limits_{i-L<=j<i}\{f_j+d_k\}$fi​=i−L<=j<imax​{fj​+dk​}
其中$k$k为$j$j到$i$i的战斗点，我们$dp$dp的时候就可以从后往前跟新战斗点，但是这样$dp$dp的时间复杂度的是$O(n^2)$O(n2)的，再套上一层二分就是$O(n^2logn)$O(n2logn)的，这就是$50$50分的部分分解法，还要优化
我们可以用单调队列来维护可能成为战斗点的点，不难发现，每个战斗点都会控制连续一段的点，从那些点到达$i$i点的战斗点都为此点，用图来理解一下

其中，涂成蓝色的点为可能战斗点，涂成红色的点为要到达的点，大括号下面的是数字为大括号上面的点到达8号点的战斗点
那么我们就可以用线段树来维护$f$f数组的区间最值，然后再用一棵平衡树来维护队列中决策的最大值，时间复杂度$O(nlog^2n)$O(nlog2n)

#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<set>
#define N 31000
using namespace std;
int n,L;
int a[N+1],b[N+1],c[N+1];
long double d[N+1];
int q[N+1];
long double tree[N<<3|1];
long double Max(long double a,long double b)
{
	return a>b?a:b;
}
void update(int p,int l,int r,int x,long double y)
{
	tree[p]=Max(tree[p],y);
	if(l==r)
		return;
	int mid=(l+r)>>1;
	if(x<=mid)
		update(p<<1,l,mid,x,y);
	else
		update(p<<1|1,mid+1,r,x,y);
}
long double query(int p,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
		return tree[p];
	int mid=(l+r)>>1;
	long double res=-2147483647;
	if(L<=mid)
		res=Max(res,query(p<<1,l,mid,L,R));
	if(R>mid)
		res=Max(res,query(p<<1|1,mid+1,r,L,R));
	return res;
}
multiset<long double> t;
multiset<long double>::iterator it;
void insert(long double x)
{
	t.insert(x);
}
void del(long double x)
{
	it=t.find(x);
	if(it!=t.end())
		t.erase(it);
}
long double MAX()
{
	if(t.size()==0)
		return -2147483647;
	it=t.end();
	it--;
	return *it;
}
bool check(long double mid)
{
	t.clear();
	for(int i=1;i<=(n<<3|1);i++)
		tree[i]=-2147483647;
	for(int i=1;i<=n;i++)
		d[i]=a[i]-b[i]*mid;
	int h=0,t=0;
	q[t]=1;
	update(1,1,n,1,d[1]);
	for(int i=2;i<=n;i++)
	{
		int l=max(1,i-L);
		while(h<=t&&q[h]<=l)
		{
			if(h<t)
				del(query(1,1,n,q[h],q[h+1]-1)+d[q[h]]);
			h++;
		}
		while(h<=t&&c[i]>=c[q[t]])
		{
			if(h<t)
				del(query(1,1,n,q[t-1],q[t]-1)+d[q[t]]);
			t--;
		}
		q[++t]=i;
		if(h<t)
			insert(query(1,1,n,q[t-1],q[t]-1)+d[q[t]]);
		long double res=-2147483647;
		res=Max(res,query(1,1,n,l,q[h]-1)+d[q[h]]);
		res=Max(res,MAX());
		update(1,1,n,i,res);
	}
	return query(1,1,n,n,n)>=0;
}
int main()
{
	scanf("%d %d",&n,&L);
	n++;
	for(int i=2;i<=n;i++)
		scanf("%d %d %d",&a[i],&b[i],&c[i]);
	long double l=0,r=10000000,exp=1e-10,mid,ans=0;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid))
			l=mid+exp,ans=mid;
		else
			r=mid-exp;
	}
	int res=0;
	while((int)ans==0)
		ans*=10,res--;
	while(ans>=10)
		ans/=10,res++;
	printf("%.9Lfe",ans);
	bool flag=(res>=0);
	if(flag)
		printf("+");
	else
		printf("-");
	res=res>0?res:-res;
	int a[4];
	a[1]=res/100;
	a[2]=res/10%10;
	a[3]=res%10;
	printf("%d%d%d",a[1],a[2],a[3]);
	return 0;
}

该代码常数巨大，开了o2才过