caioj 1080 动态规划入门（非常规DP4：乘电梯）(dp数组更新其他量)

我一开始是这么想的

注意这道题数组下标是从大到小推，不是一般的从小到大推

f[i]表示从最高层h到第i层所花的最短时间，答案为f[1]

那么显然

f[i] = f[j] + wait(j) + (j - 1), j > i

也就是说枚举从哪个楼层过来。取最优

wait（j）表示从第j个楼层等待电梯的最短时间。

这个算法应该是正确的，但是时间复杂度很大

有n个电梯，h层的话

枚举i和j要h * h,然后算wait要枚举电梯要n

所以是h * h * n，而题目给的n最大200，h最大10000,肯定超时

所以我交上去之后只拿了20分

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 212;

const int MAXM = 11234;

int x[MAXN], y[MAXN], n, h;

double f[MAXM];

double t(int i, int pos)

{

	double a = y[i] - pos, b = pos - x[i];

	return (a * (a + 1.0) + b * (b + 1.0)) / (2 * (a + b + 1.0));

}

double wait(int now, int pre)

{

	if(pre > h) return -1;

	double ret = 1e9;

	REP(i, 0, n)

		if(x[i] <= now && pre <= y[i])

			ret = min(ret, t(i, pre));

	return ret == 1e9 ? -1 : ret;

}

int main()

{

	scanf("%d%d", &n, &h);

	REP(i, 0, n) scanf("%d%d", &x[i], &y[i]); 

	f[h] = 0.0;

	for(int i = h - 1; i >= 1; i--)

	{

		f[i] = 1e9;

		int j = i + 1;

		double time;

		while((time = wait(i, j)) != -1)

		{

			f[i] = min(f[i], f[j] + time + (double)(j - i));

			j++;

		}

	}

	printf("%.5lf\n", f[1]);

	return 0;

}

然后我就想怎么优化，但是想不出来。

然后去看网上的博客关于这道题的题解

发现全部超时，20分，没有例外（没AC怎么会发出来？）

然后去看caioj视频里的讲解。

这里吐糟一下，讲解人没有把正解理解很透彻，是凑巧正确的，

所以讲不清楚……然后他就说只有高手才能看得懂，我也是醉了。

不过讲解人还是很牛逼的，想出了这么牛逼的方法。

首先有两个结论。

(1)乘电梯的人只会往下走，不会往上走。往上走一定不是最优的，浪费时间。

(2)对于一个电梯来说，知道了范围楼层中其中一个楼层的最优时间后，这个范围

楼层的所有最优时间都可以推出来。比较抽象，我解释一下。对于当前电梯，

假设是从3楼到7楼，那么，如果到第5楼的最优时间是20秒，那么第6楼的最优时间

就说19秒，第4楼的最优时间就是21秒（注意这里最优是只看当前电梯，与其他电梯无关）

也就是说知道了一个楼层的最优时间就可以推出这个范围内所有楼层的最优时间（再次强调，

这里指的是对当前电梯来说）理解这一点是正解的精髓所在。

这意味着，当我们推出了某个楼层的最优时间后，我们

可以反过来把所有包含当前楼层的电梯的最优时间都更新一遍。

下一次算的时候可以直接使用。

为了方便起见，每个电梯都统一为到最上的楼层的时间。

比如当前电梯时3到7,那么我们知道了到第5楼的最短时间是20秒，

那么我们存的时候就存第7楼是18秒，第7楼是最上面的楼层。

那么下次枚举到这个电梯的时候，如果是第3层的话，所花

时间就是18 + 4 = 22秒。这样统一一下很方便。

所以大致思路就是这样，每次推出当前楼层最优值后都去更新

每一个电梯的最优时间。

这和之前的题都不一样，之前的题是其他量和前面的dp数组推出

当前的dp数组，而这道题还多了用当前dp数组去推其他量，从而

为后来的dp数组计算。

这样可以说把动态规划的特性用到了极致。

秀！

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 212;

const int MAXM = 11234;

int x[MAXN], y[MAXN], n, h;

double f[MAXM], d[MAXN];

double t(int j, int pos)

{

	double a = y[j] - pos, b = pos - x[j];

	return (a * (a + 1.0) + b * (b + 1.0)) / (2 * (a + b + 1.0));

}

int main()

{

	scanf("%d%d", &n, &h);

	REP(i, 0, n) scanf("%d%d", &x[i], &y[i]), d[i] = 1e9; 

	memset(f, 0x43, sizeof(f));

	f[h] = 0.0;

	for(int i = h; i >= 1; i--)

	{

		REP(j, 0, n)

			if(x[j] <= i && i <= y[j])

			{

				int k = y[j] - i; //k是当前楼层在这个电梯中的位置。如3~7,第5层的位置就是2

				f[i] = min(f[i], d[j] + k); //从最上的楼层走到当前楼层

			}

		REP(j, 0, n)

			if(x[j] <= i && i <= y[j])

			{

				int k = y[j] - i;

				d[j] = min(d[j], f[i] + t(j, i) - k);//减去k是为了推最上的楼层

			}

	}

	printf("%.5lf\n", f[1]);

	return 0;

}

但是这道题还再优化！

看代码会发现，f数组其实可以省掉

因为只需要用到f[i]

所以我们可以用一个变量来代替f数组

当然初始化要和原来保持一致

i = h时是0，其余是无穷大

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 212;

const int MAXM = 11234;

int x[MAXN], y[MAXN], n, h;

double ans, d[MAXN];

double t(int j, int pos)

{

	double a = y[j] - pos, b = pos - x[j];

	return (a * (a + 1.0) + b * (b + 1.0)) / (2 * (a + b + 1.0));

}

int main()

{

	scanf("%d%d", &n, &h);

	REP(i, 0, n) scanf("%d%d", &x[i], &y[i]), d[i] = 1e9; 

	for(int i = h; i >= 1; i--)

	{

		if(i == h) ans = 0.0;

		else ans = 1e9;

		REP(j, 0, n)

			if(x[j] <= i && i <= y[j])

			{

				int k = y[j] - i; //k是当前楼层在这个电梯中的位置。如3~7,第5层的位置就是2

			    ans = min(ans, d[j] + k); //从最上的楼层走到当前楼层

			}

		REP(j, 0, n)

			if(x[j] <= i && i <= y[j])

			{

				int k = y[j] - i;

				d[j] = min(d[j], ans + t(j, i) - k);//减去k是为了推最上的楼层

			}

	}

	printf("%.5lf\n", ans);

	return 0;

}

巴特西

caioj 1080 动态规划入门（非常规DP4：乘电梯）(dp数组更新其他量)

最新文章

热门文章