复杂题意下的DP做题模式

前言

首先，可以肯定的一点是，DP 题目很好看出来，因为一般具有明显的求最值、多过程转移的特征；其次，DP 题目也不是很好看，因为 DP 本质上是对暴力枚举的贪心优化，形式上可以是图论遍历、树的遍历、序列遍历。

DP 本身不难，难就难在如何用。
以P11290 【MX-S6-T2】「KDOI-11」飞船为例题，来详细思索一下。

正文

首先，题目大致是说从起点出发，笔直的道路上有一些加速站，对于加速站

i

，可以花费额外的时间

t_i

使原来的速度翻为

x_i

倍，效果叠加。
然后给出多个询问

y_i

，表示询问到

y_i

至少花费多少时间。
其余注意事项，精度小数点后 6 位；效果可以叠加；询问距离上限

10^9

，最多

10^5

个加速站。

此题看似困难，但实际上我们可以很快联想到背包问题，类似地对于每个加速站选择是否加速。
但是显然的问题是，每一次加速后由于效果叠加，所以是有后效性，其体现就是下述做法的错误:

\scriptsize\text{对于每个加速站，得到到达加速站的最小耗时及其时的速度，对于每个询问}

\scriptsize\text{点，枚举其前的每一个加速站，以此得到询问点的“最小耗时”。}

显然，样例都不给过。在样例中，到达最后一个加速站的最短耗时方案是在第三个加速站时不加速（第一个加速站显然也不加速），然而到达最后一个询问点需要在第三个加速站，计算可得按上述方案最后一个询问得到答案

259.5

，显然并不正确。

然而回到背包问题，背包也是有后效性的，对于放一个物品，背包剩余可用体积会变，于是被记入状态。
类似的，于是我们也可以把速度记入状态，状态表示最短耗时。形式化地 ~~非口糊地~~ 说，可以设计得到状态转移方程如下：

f_{i,j}=\min(f_{i-1,j}+\frac{\Delta p}{j},f_{i-1,\frac{j}{x_i}}+\frac{\Delta p\cdot x_i}{j})

其中

f_{i,j}

表示到达

i

位置时速度为

j

的最小耗时。

但是仅仅如此还不够，因为按照距离转移，根本跑不了。所以要用技巧。
观察发现，在范围

10^9

的距离中，有一些位置的耗时是没必要知道的，我们只想要询问的位置、加速站的位置时的即可。于是离散化。

然而可知，速度最多可以加速

10^5

次，也即理论上来讲，最高时速

4^{10^5}

，貌似速度这一维撑爆了，但是对于

10^9

距离来讲

2^{32}

的速度一秒以内就跑完，并且对于一个加速站，最少花费的额外时间为

1

秒，所以说从

2^{32}

花一秒加速到

2^{33}

去跑

10^9

距离不会比不加速更优，也即最多加速

\lceil\log_2 10^9\rceil

次。但是也不可能把这么多的速度设到状态转移里。观察发现，

1\leq x_i\leq 4

，所以能够得到的所有速度必然有形式为

v=2^i\times 3^j,i,j\scriptsize\text{为非负整数}

，于是重新调整状态表示为

f_{k,i,j}

表示到达第

k

个离散化的点速度为

2^i\times 3^j

的最少时间。还发现

k

只与

k-1

相关，所以滚动数组。

然后code，其中离散化可以使用map或者二分。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long double ldb;
const int N = 1000810,M2 = 33,M3 = 28;
const ldb inf = 1e17;
int n,q;
int read(){
	int res=0;
	char ch=getchar();
	while(ch<'0' || ch>'9')	ch=getchar();
	while(ch>='0' && ch<='9')
		res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
	return res;
}

struct dote{
	int py;
	int t,x;
	dote(){
		py=0,t=0,x=1;
	}
	bool operator<(const dote &o)const {
		return py<o.py;
	}
}sp[N*2];
int nu;

ldb ans[N];//离散化后的第 k 点的最短耗时

ldb f[2][M2][M3];//滚动转移
int qs[N];

int m=1,m2=0,m3=0;

void solve(){
	for(int i=1;i<=nu;i++)	ans[i]=1e17;
	for(int i=0;i<M2;i++)
		for(int j=0;j<M3;j++)
			f[1][i][j]=f[0][i][j]=inf;
	f[0][0][0]=0;//init
	m2=0,m3=0;
	for(int k=1,s,t,x;k<=nu;k++){
		t=sp[k].t;x=sp[k].x;
		s=sp[k].py-sp[k-1].py;
		if(x==2)	m2++;
		if(x==4)	m2+=2;
		if(x==3)	m3++;
		m2=min(m2,M2-1),m3=min(m3,M3-1);
		//m2,m3规约每一次转移的范围，节省常数
		
		for(int i=0;i<=m2;i++)
			for(int j=0;j<=m3;j++)	f[k&1][i][j]=inf;//init
		
		for(int i=0,v2=1;i<=m2;i++,v2*=2){
			for(int j=0,v3=1;j<=m3;j++,v3*=3){
				f[k&1][i][j]=min(f[k&1][i][j],f[(k&1)^1][i][j]+(ldb)s/(v2*v3));
				if(x==2 && v2>=2)
					f[k&1][i][j]=min(f[k&1][i][j],f[(k&1)^1][i-1][j]+(ldb)s/(v2/2*v3)+t);
				if(x==3 && v3>=3)
					f[k&1][i][j]=min(f[k&1][i][j],f[(k&1)^1][i][j-1]+(ldb)s/(v2*v3/3)+t);
				if(x==4 && v2>=4)
					f[k&1][i][j]=min(f[k&1][i][j],f[(k&1)^1][i-2][j]+(ldb)s/(v2/4*v3)+t);
				ans[k]=min(ans[k],f[k&1][i][j]);
			}
		}
	}
}
/*
f'[i][j]=min(f[i][j]+(py'-py)/v(i,j),
f[i][j-1]+(py'-py)/v(i,j-1)+t, x'=3
f[i-1][j]+(py'-py)/v(i-1,j)+t, x'=2
f[i-2][j]+(py'-py)/v(i-2,j)+t, x'=4)
*/
vector<int> dis;//离散列表

int main(){
	n=read(),q=read();
	for(int i=1;i<=n;i++)
		sp[i].py=read(),sp[i].t=read(),sp[i].x=read();
	nu=n;
	for(int i=1,a;i<=q;i++){
		a=read();
		sp[++nu].py=a;
		sp[nu].x=1;//当作没有加速意义的点
		qs[i]=a;
	}
	sort(sp+1,sp+nu+1);//离散化
	solve();
	for(int i=1;i<=nu;i++)	dis.push_back(sp[i].py);
	for(int i=1;i<=q;i++){
		int id=lower_bound(dis.begin(),dis.end(),qs[i])-dis.begin()+1;
		//二分查找
		printf("%.6Lf\n",ans[id]);
	}
	return 0;
}

后记

区区3000字小题解写什么后记……

其实可以看出，更难的题目往往不是算法本身难，而是转化的点、细节、算法技巧配合的更多。

其实写着是颇为不甘的，明明花了大把力气搞 DP，结果还是无法场切。

不甘的事多了去了，结束吧。

——2024/11/23

~~斐波那契日？~~

复杂题意下的DP做题模式

文章操作

前言

正文

后记

相关推荐

评论

复杂题意下的DP做题模式