原題傳送:http://acm.hdu.edu.cn/showproblem.php?pid=3697
貪心算法。起始點可能是0,1,2,3,4,枚舉這5個起始點,後面的點選擇可選政策是:選擇符合該時刻且結束時間最早的。
View Code
1 #include <stdio.h>
2 #include <string.h>
3 #define N 305
4 struct course
5 {
6 int s, t;
7 }e[N];
8
9 int n;
10 bool vis[N];
11
12 void work()
13 {
14 int ans, i, j, k, x, max;
15 max = 0;
16 for(i = 0; i < 5; i ++)
17 {
18 memset(vis, false, sizeof vis);
19 ans = 0;
20 for(j = i; j <= 1000; j += 5)
21 {
22 x = -1;
23 for(k = 0; k < n; k ++)
24 {
25 if(!vis[k] && e[k].s <= j && e[k].t > j)
26 if(x == -1 || e[k].t < e[x].t)
27 x = k;
28 }
29 if(x != -1)
30 ans ++, vis[x] = true;
31 }
32 if(ans > max)
33 max = ans;
34 }
35 printf("%d\n", max);
36 }
37
38 void read()
39 {
40 for(int i = 0; i < n; i ++)
41 scanf("%d%d", &e[i].s, &e[i].t);
42 }
43
44 int main()
45 {
46 while(scanf("%d", &n), n)
47 {
48 read();
49 work();
50 }
51 return 0;
52 }
轉載于:https://www.cnblogs.com/huangfeihome/archive/2012/09/13/2683096.html