題目連結 UVa
題目連結 POJ
題目連結 HDU
題目連結 UvaLive
題目連結 SCU
題目連結 OpenJ_Bailian1040
- 題意：有一列火車從 A(0 號車站) 開到 B(m 號車站)，路上經過車站依序編號為 0 到 m，現在有 t 筆訂單，每筆訂單有人數，起點和終點，如果接受這筆訂單，就可以獲得人數 × 經過站數(終點-起點)，火車最多可以載 n 位客人，求最高獲益。
- 題解：遞迴爆搜，利用前綴和和差分檢查如果加入當前訂單，車上的容量是否足夠。另外需要剪枝，當前的已接受的訂單 + 還沒確定是否要接受的訂單，所有獲益無法成為最佳解即停止搜索。
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
using namespace std;
typedef long long LL;
struct Data
{
int s, t, n, cost;
bool operator<(const Data &rhs) const { return cost < rhs.cost; }
};
int n, b, t;
int ans;
vector<int> costSum(25), sum(10);
vector<Data> v;
void doit(int d, int dir)
{
sum[v[d].s] += dir * v[d].n;
sum[v[d].t] -= dir * v[d].n;
}
bool ok()
{
int total = 0;
for (int i = 0; i <= b; ++i)
{
total += sum[i];
if (total > n)
{
return false;
}
}
return true;
}
void dfs(int d, int cur)
{
// cout << d << ' ' << cur << '\n';
ans = max(ans, cur);
if (d == t)
{
return;
}
if(cur + costSum[d] <= ans)
{
return;
}
doit(d, 1);
if (ok())
{
dfs(d + 1, cur + (v[d].t - v[d].s) * v[d].n);
}
doit(d, -1);
dfs(d + 1, cur);
return;
}
int main()
{
while (cin >> n >> b >> t, n || b || t)
{
v.resize(t);
fill(sum.begin(), sum.end(), 0);
fill(costSum.begin(), costSum.end(), 0);
for (int i = 0; i < t; ++i)
{
cin >> v[i].s >> v[i].t >> v[i].n;
v[i].cost = v[i].n * (v[i].t - v[i].s);
}
sort(v.begin(), v.end());
for (int i = t - 1; i >= 0; --i)
{
costSum[i] = costSum[i + 1] + v[i].cost;
}
ans = 0;
dfs(0, 0);
cout << ans << '\n';
}
}
如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)
