总结
1. 这种状态转移的题目不太好 debug, 写起来总觉得不对劲
2. 动规的初始化总能找到一些简练的初始化方法, 比如这道题, 可以选择 j>=0, dp[0] = 1, 或者对 vector 中的所有元素赋值 dp[s] = 1, 然后 j > 0
代码 TLE 了
|
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96 |
/* * source.cpp * * Created on: Apr 6, 2014 * Author: sangs */#include <stdio.h>#include <iostream>#include <string>#include <vector>#include <memory.h>#include <algorithm>#include <math.h>using
namespace std;int
arr[100];vector<int> state;int
dp[100100];bool
cal(int
n, int
si, int
load1, int
load2) { int
sum = 0; bool
dp1[200]; memset(dp1, 0, sizeof(dp1)); dp1[0] = true; for(int
i = 0; i < n; i ++) { if(((1<<i) & si )== 0) continue; sum += arr[i]; if(arr[i] > load1) continue; for(int
j = load1; j >= arr[i]; j -- ) { dp1[j] |= dp1[j-arr[i]]; } } int
sum1 = 0; for(int
i = load1; i >= 0; i --) { if(dp1[i]) { sum1 = i; break; } } if(sum-sum1 <= load2) return
true; return
false;}void
func1(int
n, int
load1, int
load2) { int
endState = (1<<n); for(int
i = 1; i < endState; i++) { if(cal(n, i, load1, load2)) { state.push_back(i); } }}int
solve_dp(int
n) { memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for(size_t
i = 0; i < state.size(); i ++) { for(int
j = (1<<n)-1; j >= 0; j --) { dp[j|state[i]] = min(dp[j|state[i]], dp[j]+1); } } return
dp[(1<<n)-1];}int
main() { freopen("input.txt", "r", stdin); int
cases; scanf("%d", &cases); int
seq = 0; while(cases --) { seq ++; int
n, load1, load2; scanf("%d%d%d", &n, &load1, &load2); for(int
i = 0; i < n; i ++) scanf("%d", arr+i); func1(n, load1, load2); int
res = solve_dp(n); printf("Scenario #%d:\n%d\n\n", seq, res); } return
0;} |
POJ 2923 Relocation(状态压缩DP),布布扣,bubuko.com
原文：http://www.cnblogs.com/zhouzhuo/p/3649500.html