总结
1. dp[i][j] 第二个变量 j 的设置. j 可以设置成 Money, 也可以是带宽. 分别写一下状态转移方法会发现 j 是带宽时简单些, 并且带宽枚举量少一下
2. dp[i][j] = min(dp[i][j], price[i][k]+dp[i-1][j]) for all k that bw[i][k] >= j
代码 WA. discuss 的测试数据都通过了, 可能是 dp[-1] 的问题, 以后再改吧
|
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 |
/* * source.cpp * * Created on: 2014-4-5 * Author: vincent *//* * dp[i][j] 前 i 件设备, 最大带宽为 j 时的最小花费 */#include <iostream>#include <stdio.h>#include <memory.h>#include <math.h>using
namespace std;int
bw[110][110];int
price[110][110];int
manu[110];int
dp[110][10010];double
cal(int
n, int
MAXBW) { memset(dp, 0x3f, sizeof(dp)); for(int
i = 0; i < n; i ++) { for(int
j = 0; j <= MAXBW; j ++) { for(int
k = 0; k < manu[i]; k ++) { if(bw[i][k] < j) continue; dp[i][j] = min(dp[i][j], dp[i-1][j]+price[i][k]); } } } double
ret = 0.0; for(int
j = 0; j <= MAXBW; j ++) { ret = max(ret, 1.0*j/dp[n-1][j]); } return
ret;}int
main() { int
cases; int
devices; int
n, MAXDW; freopen("input.txt", "r", stdin); scanf("%d", &cases); while(cases --) { MAXDW = 0; scanf("%d", &devices); for(int
i = 0; i < devices; i ++) { scanf("%d", &n); manu[i] = n; for(int
j = 0; j < n; j ++) { scanf("%d%d", &bw[i][j], &price[i][j]); MAXDW = max(MAXDW, bw[i][j]); } } double
res = cal(devices, MAXDW); printf("%.3f\n", res); } return
0;} |
POJ 1018 Communication System(二维DP),布布扣,bubuko.com
POJ 1018 Communication System(二维DP)
原文：http://www.cnblogs.com/zhouzhuo/p/3646945.html