传送门
贪心法。
贪心策略就是优先选开始时间较晚的节目 或者 优先选结束时间较早的节目,先排序,然后一遍顺序求解。
如果要求的不是节目个数最大,而是节目总时长最大(或者每个节目都有一个价值,要求总价值最大),该怎么解决呢?
(5月7日)设想每个节目都有一个价值,要求选的总价值最大。可以这么考虑,对每个时间单位从小到大进行dp,dp[i]
表示时间范围为0~i
的子问题的最优解。
d
p
[
i
]
=
max
(
d
p
[
i
−
1
]
,
max
e
n
d
[
x
]
=
i
(
d
p
[
i
−
s
p
e
n
d
[
x
]
]
+
v
a
l
u
e
[
x
]
)
)
dp[i]=max(dp[i-1],max_{end[x]=i}(dp[i-spend[x]]+value[x]))
dp[i]=max(dp[i−1],end[x]=imax(dp[i−spend[x]]+value[x]))
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#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <cstring> #include <string> #include <queue> using namespace std; // 区间贪心 int N; int ans; struct interval { int a, b; bool operator<(const interval& i0) const { return a > i0.a; } }; vector<interval> v; void init() { v.clear(); ans = 1; } int main() { int a, b; for (; ~scanf("%d", &N);) { if (N == 0) break; init(); for (int i = 0; i < N; i++) { scanf("%d%d", &a, &b); v.push_back(interval{ a,b }); } sort(v.begin(), v.end()); int prev = v[0].a; for (int i = 1; i < N; i++) { if (v[i].b <= prev) { ans++; prev = v[i].a; } } printf("%dn", ans); } return 0; }
最后
以上就是和谐高山最近收集整理的关于HDU 2037 今年暑假不AC的全部内容,更多相关HDU内容请搜索靠谱客的其他文章。
发表评论 取消回复