[codevs4438] YJQ Runs Upstairs #patina27大战玄学#

发表于   |  

题目本身是好题

题目描述 Description

学校科技楼一共有N层,而神犇YJQ每天都在科技楼N楼的机房写代码。这天,他准备从科技楼1楼爬到N楼。有个M连接不同楼层的楼梯,爬每个楼梯需要一定的体力值。楼梯一定是从低处通往高处的。(但是由于楼房的设计比较奇怪,第i楼并不一定在第i-1楼上面,也就是说给出的边不保证x<y,但保证图为DAG,请自行处理楼层之间的高度关系)。为了省时间,YJQ一定只会上楼梯而不会下楼梯,即楼梯间不会形成环路。而且出于人性化考虑,不管YJQ选择什么路线上楼,他爬的楼梯数量一定小于20。为了使体力消耗尽量平稳,YJQ需要选择一条“每个楼梯消耗体力值的方差最小”的路径上楼。请帮助YJQ计算出这个最小方差。

输入描述 Input Description

第一行包含2个整数N,M表示科技楼楼层数和楼梯数; 接下来M行,每行3个数,x,y,z表示存在一条由x层通往平台y层的楼梯,爬这个楼梯需要消耗z的体力值。

输出描述 Output Description

一行1个实数,表示最小方差,精确到小数点后4位。

样例输入 Sample Input

4 4 1 2 1 2 4 3 1 3 2 3 4 3

样例输出 Sample Output

0.2500

数据范围及提示 Data Size & Hint

对于30%的数据,N<=10,M<=20;
另有20%的数据N<=35,M<=220,Z∈0,1;
对于100%的数据2<=N<=50,M<=300,0<=Z<=50保证至少存在一条由1到N的路径。

Solution

我们考虑方差的计算公式
(图丢了QAQ)
所以我们可以考虑动态规划,dp[i][j][k]表示走到i号点，走了j条边并且边权和为k的最小边权平方和，最终的答案是走到i号点时枚举一下走了多少条边与边权和为多少，并以此计算答案。可以证明最小方差一定在所有的状态之中
复杂度：O(202050*M)(20是最大边数，50是每条边的最大权值)

这个处理方差的做法是可以推广的

实际是绝对方差值的有三个因素

  1. 元素个数
  2. 元素和
  3. 元素平方和

本题的思想就是控制其中的两个变量，另剩余的一个变量最小。

经过美化后的代码（visual studio最强功能 ctrl+k,ctrl+d 格式化代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXM 300+1
#define INF 1000000000
#define MAXN 50+1
#define MAXdep 20+1
#define min(a,b) (a>b)?b:a
using namespace std;
struct Data {
	int v, w, nex;
} data[MAXM]; int fir[MAXN];
int e = 0;
void addedge(int x, int y, int z) {
	data[++e].v = y;
	data[e].w = z;
	data[e].nex = fir[x];
	fir[x] = e;
}
int q[10000], h = 0, t = 0;
int U[MAXN], cnt = 0;
int inq[MAXN];
int f[MAXN][MAXdep][50 * MAXM];
int n, m, sum = 0;
void topo() {
	memset(f, 127, sizeof f);
	const int inf = f[1][0][0];
	f[1][0][0] = 0;
	for (int i = 1; i <= n; i++) if (!inq[i]) q[++t] = i;
	while (h < t) {
		int u = q[++h];
		for (int j = 0; j <= 20; j++)
			for (int k = 0; k <= sum; k++)
				if (f[u][j][k] != inf)
					for (int p = fir[u]; p > 0; p = data[p].nex) {
						int v = data[p].v, w = data[p].w;
						if (j + 1 <= 20 && w + k <= sum)
							f[v][j + 1][w + k] = min(f[v][j + 1][w + k], f[u][j][k] + w*w);
					}
		for (int i = fir[u]; i; i = data[i].nex) {
			int v = data[i].v;
			if (!--inq[v])
				q[++t] = v;
		}
	}
}
int main() {
	freopen(""1.in"", ""r"", stdin);
	freopen(""1.out"", ""w"", stdout);
	scanf(""%d%d"", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		scanf(""%d%d%d"", &x, &y, &z);
		addedge(x, y, z);
		inq[y]++;
		sum += z;
	}
	topo();
	double ans = INF;
	for (int j = 1; j <= 20; j++)
		for (int k = 0; k <= sum; k++)
			ans = min(ans, ((double)f[n][j][k] / (double)j) - (double)(k*k) / (double)(j*j));
	printf(""%.4f"", ans);
	fclose(stdin); fclose(stdout);
	return 0;
}

My Story

  1. 一开始maxn写成40了orz
  2. 发现maxm也写错了
  3. 改了还不对
  4. 发现输出有负数。。。。
  5. 猛然发现需要拓扑排序。。。
  6. 拓扑完还错
  7. 拓扑打错了 应该一开始把所有入度为0的都入队，支线也会对主线有影响
  8. 还是错
  9. 无奈造数据。。
  10. 数据造太差 人工调
  11. 发现负数
  12. 调试的时候发现当程序吧数组的某一个值赋值时，数组中的别的元素居然有干扰。。。
    举个例子 赋值f[5][1][10]=100后， f[5][0][810]的值也变成了100
  13. 对此玄学陷入深深的惶恐。。。
  14. 发现如果不用宏定义就好了 即int f[maxn][maxn][maxm*50] 改成普通形式
  15. ac了
  16. 发现用宏定义只要数组不开大也没事。
  17. 得出结论c++果然是玄学
  18. 教训：以后数组千万别乱开啊啊啊

“