题解：P11290 【MX-S6-T2】「KDOI-11」飞船

这题我赛时没想出正解，在赛后才明白怎么做。

首先通过推导公式，发现该题无法贪心。

然后我想到一个 dp，以第几个加油站为第一维，以速度为第二维，可以轻松通过速度转移状态。但是这样 dp 会使速度达到指数级别，简直爆炸。

赛后我反应过来，虽然速度的值域看似达到指数级，但速度的个数远远没有达到这种数量。为什么呢？

首先我们发现速度值域根本没有这么大，因为如果速度过大，会导致加速减少的时间很少，而在加油上浪费了更多的时间，不是最优解。而加速减少的时间至少为

1

，即速度值域上界则为

p

的值域上界。

但这样也 AC 不了。我们继续推导发现燃油编号为

1

可以忽略不计，为

4

可以拆成两个

2

，所以速度一定是

2

的非负整数次方乘上

3

的非负整数次方。

这样 dp 就很好转移了。第一维表示第几个加油站，第二维表示

2

的指数，第三维则表示

3

的指数，然后通过加油站转移状态即可。查询时，首先找到最后一个小于等于目标节点的加油站（可以使用二分），然后从这个加油站的每个状态转移出答案，并取最小值即可。

这样我们就得到了一个

O(n\log^2 n)

的算法。由于空间耗用较大，考虑使用滚动数组优化 dp，且把询问离线下来升序排序，边转移边处理询问，这会把空间优化至线性，还会意外地使时间得到优化。

AC 代码：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005][3],x,y,z,num=1,g2[5]={0,0,1,0,2},g3[5]={0,0,0,1,0};
long long p2[30],p3[19];
double c[30][19],d[30][19],aans,ans[100005];
struct node
{
	int id,x;
} b[100005];
bool operator<(node x,node y)
{
	return x.x<y.x;
}
int main()
{
	cin>>n>>m;
	for (int i=1;i<=n;++i)
	scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
	a[n+1][0]=0x7fffffff;
	for (int i=1;i<=m;++i)
	{
		b[i].id=i;
		scanf("%d",&b[i].x);
	}
	sort(b+1,b+m+1);//离线处理
	p2[0]=1;
	p3[0]=1;
	for (int i=1;i<=29;++i)
	p2[i]=p2[i-1]<<1;
	for (int i=1;i<=18;++i)
	p3[i]=3*p3[i-1];//预处理2、3的幂次方
	for (int i=0;i<=29;++i)
	for (int j=0;j<=18 && p2[i]*p3[j]<=1000000000;++j)
	c[i][j]=1e18;
	c[0][0]=0;//预处理
	for (int i=1;i<=n;++i)
	{
		x=a[i][0];
		y=a[i][1];
		z=a[i][2];
		memcpy(d,c,sizeof(c));//滚动数组
		for (int j=0;j<=29;++j)
		for (int k=0;k<=18 && p2[j]*p3[k]<=1000000000;++k)
		{
			c[j][k]=d[j][k]+(double)(x-a[i-1][0])/(p2[j]*p3[k]);
			if (j>=g2[z] && k>=g3[z])
			c[j][k]=min(c[j][k],d[j-g2[z]][k-g3[z]]+(double)(x-a[i-1][0])/(p2[j-g2[z]]*p3[k-g3[z]])+y);
		}//转移速度
		for (num;num<=m && b[num].x<=a[i+1][0];++num)
		{
			aans=1e18;
			for (int j=0;j<=29;++j)
			for (int k=0;k<=18 && p2[j]*p3[k]<=1000000000;++k)
			aans=min(aans,c[j][k]+(double)(b[num].x-x)/(p2[j]*p3[k]));
			ans[b[num].id]=aans;
		}//处理询问
	}
	for (int i=1;i<=m;++i)
	printf("%.9lf\n",ans[i]);//使用printf以减小误差
}

题解：P11290 【MX-S6-T2】「KDOI-11」飞船

文章操作

相关推荐

评论

题解：P11290 【MX-S6-T2】「KDOI-11」飞船