纳米的OI博客

题目大意：
飞机飞行高度在[20000,40000]，必须是1000的倍数。正常飞行高度是30000，每小时耗油量是2000。飞行高度与正常高度每相差1000，每小时就需要增加耗油量10。每爬升高度1000，需要耗油50。
现在要飞行n个区域，每个区域有给定的长度和高度20000时风速和高度40000时风速，风速和高度成线性关系。飞行速度是400+风速。求最小耗油量以及高度方案。

解题方法：
简单动态规划题，以区域和高度作为状态。

注意事项：
最后输出是整数，四舍五入吗？那你就悲剧了^^

代码：

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

#include <cmath>
#include <cstdio>
#include <cstdlib>
 
const double INF = 1e10;
 
const int maxn = 101, maxh = 21;
int n, len[maxn], speed[maxn][2], table[maxn][maxh], ans_project[maxn];
double dp[maxn][maxh], answer;
 
int input() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d%d%d", &len[i], &speed[i][0], &speed[i][1]);
	return 0;
}
 
int solve() {
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j < maxh; ++j)
			dp[i][j] = INF;
	dp[0][0] = 1000;
	for (int i = 1; i <= n; ++i) {
		double unit = (speed[i][1] - speed[i][0]) / (maxh - 1.0);
		for (int j = 0; j < maxh; ++j) {
			double datum = (2000 + abs(j - 10) * 10) * (len[i] / (400 + speed[i][0] + unit * j));
			for (int k = 0; k < maxh; ++k) {
				double tmp = dp[i - 1][k] + datum + (j > k ? (j - k) * 50 : 0);
				if (tmp < dp[i][j]) {
					dp[i][j] = tmp;
					table[i][j] = k;
				}
			}
		}
	}
	answer = INF;
	for (int i = 0; i < maxh; ++i)
		if (dp[n][i] < answer) {
			answer = dp[n][i];
			ans_project[n] = i;
		}
	for (int i = n - 1; i > 0; --i)
		ans_project[i] = table[i + 1][ans_project[i + 1]];
	return 0;
}
 
int output(int t) {
	printf("Flight %d: ", t);
	for (int i = 1; i <= n; ++i)
		printf("%d ", ans_project[i] + 20);
	printf("%.0f\n", ceil(answer));
	return 0;
}
 
int main() {
	int testCases;
	scanf("%d", &testCases);
	for (int t = 1; t <= testCases; ++t) {
		input();
		solve();
		output(t);
	}
	return 0;
}

第一场：

A:另类的异或
纯水题一道，N进制无进位加法。

B:有道搜索框
赤裸裸的Trie解决，首先把所有的单词添加道Trie树里面，然后进行dfs搜索，输出前8个满足前缀的。

C:最大和子序列
看到题目我首先考虑DP，然后没有什么直观思路，转而考虑贪心。WA了一次，JMH师兄：贪心显然是错的，提供一种解决方案：

f1[i] 表示[1, i]的最大子序列和
f2[i] 表示[i, n]的最大子序列和
f3[i] 表示[1, i]的最小子序列和
f4[i] 表示[i, n]的最小子序列和
“然后你就会做了”

实践过程中，发现利用f3 f4计算跨n – 1的最大值的时候，会出现f3 f4覆盖掉所有的情况。具体怎么解决，我是分别判断f3、f4所对应区域的和是否等于f3、f4的值，如果等于不要。不知道这种方法是否完备。

第二场：

A:有“道”难题
水题，不过我把数组开小了WA了一次。有两种解决方案：
1. 把字符串读入，转换，然后统计
2. 逐个字符读入，把当前字符和前一个字符拼在一起，用二进制检查，统计。

B:有道饭团
彻底的水题，就是统计下哪个数大而已。具体实现的问题就是对姓名的编号和排序，对姓名的编号提供3种解决方案：
1. 预读入，处理，然后再处理的时候二分查找
2. HASH
3. STL里面的map，我中途去学这个了

C:有道招聘
明显的DP。我发现我也几乎只会做这样的DP了。用f(i, j)表示第i个Leader最后一个录用的人为j。记p[i]为Leader i前一位应聘者的编号。显然，有pos[i] <= j <= pos[i+1]。我开始还搞错了，以为状态总数是O(n^2)，实际是O(n)。转移：
f(i, j) = sum{ f(i-1, k) | [k+1, j]的员工满足Leader i的需要 }，转移时间为O(nm)，总时间复杂度为O(n^2*m)
对于每个(i, j)，决策范围k显然是连续的。并且对于每一个，记f(i, j)决策时最大的k为K(i, j)。对于每一个固定i，K(i, j)是关于j单调的。那么，转移可以优化，新的均摊时间复杂度为O(m)，所以总时间复杂度为O(nm)。

第三场：

A:选课的困惑
Problem A终于不那么水了（其实是因为我WA了一次才那样说的 – -）。
具体做法就是，每次挑选一个未选的选修科目，并且选中的科目，是所有可挑选的科目当中，使得平均分最大的。这样不断重复，直到平均分达到90分，或者所有科目都选择后仍然不能使得平均分达到90分。

B:X星球的身份证系统
好像和以前做过某道题类似，我们以一个特定的数据分析：BCDEF
由于需要回文，所以只有前三位的决策是有意义的，进行具体分析。
1. 第1位：如果选择A，那么第2、3位都是可以随便选择的，总数为1*26^2。如果选择B，考虑第2点：
2. 第2位：如果选择A、B，那么第3为是可以随便选择的，总数为2*26^1。如果选择C，考虑第3点：
3. 第3位：如果选择A、B、C，那么总数为3*26^0。如果选择D，考虑第4点：
4. 此时，1、2、3位都已经选定，我们只需要判断这个特定的回文是否超过了给定数据。没有超过就往总数上加1，超过就无视。这样就解决了。

C:火柴游戏
这道题开始分析就往数学方面考虑。没有做出来，晚上很愤怒地把黑书带了回去看数论。结果早上回来，看到JMH师兄说了一句（我昨晚问过）：不就是DP么？
然后还是还无思路，于是去翻竞赛系统的讨论区。终于翻到了一段话：

用d[i,j]表示用了i根火柴棍后组成的数mod m的结果是j的数的个数
状态转移过程是，在[0,10)内枚举k,则状态d[i,(j*10+k)%m]可以转移到状态d[i-stick[k]][j]。其中stick[k] 表示k这个数需要多少根火柴棍。

然后好像明白了，实现之。不过又发现问题了，为什么(j*10+k)%m可以由j转移而来呢？然后突然想到昨晚黑书中看到的：

如果a1≡a2(mod m)，b1≡b2(mod m)，那么a1+b1≡a2+b2(mod m)

好了，这样就没问题了。具体还有就是状态储存问题，直接定义f[maxn][maxm]肯定要爆掉的。可以定义*f[maxn]，然后动态开new int [m]。那样就没问题了。

免得某人说我懒，顺便测试功能