我是靠谱客的博主 和谐高山,这篇文章主要介绍HDU 2037 今年暑假不AC,现在分享给大家,希望可以做个参考。

传送门

贪心法。

贪心策略就是优先选开始时间较晚的节目 或者 优先选结束时间较早的节目,先排序,然后一遍顺序求解。

如果要求的不是节目个数最大,而是节目总时长最大(或者每个节目都有一个价值,要求总价值最大),该怎么解决呢?
(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[i1],end[x]=imax(dp[ispend[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内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(80)

评论列表共有 0 条评论

立即
投稿
返回
顶部