問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1167參考:
http://angels1.0.blog.163.com/blog/static/84580504200892072639857/思路:
這題比我想象的要難好多，可以說，在看了別人AC代碼之后，發現已經超越了我目前的能力
我自己的想法很簡單，暴力搜索每條可能的路線，枚舉每條路線的前兩個點，DFS，結果始終是TLE
正確思路:
特別需要注意理解清楚題意：
Buses on the same route arrive at regular intervals from 12:00 to 12:59 throughout the entire hour.
如果找出前兩個點，那么這條路徑上的后續點也必須存在
對輸入進行預處理，找出所有可能的路徑，并且按照路徑中點的個數的多少降序排列（因為題意要求使得路線盡可能的少，所以首先搜索包含點個數最多的路徑）
另外，還有一些簡單的數學推導:
start - interval < 0 (1) [點start之前不能存在其他點]
59 - interval > start (2)
根據(1), (1)我們就可以知道start <= 29
代碼中還有一處非常重要的減枝(不剪就會TLE)：
只寫 r_cnt+1>=min還是會TLE
1 /* important pruning */
2 if(r_cnt+1+(left-routes[k].stops)/routes[k].stops >= min)
3 return;
4
代碼(TLE):
1 void
2 dfs(int begin, int cur_routes)
3 {
4 int i, j, k, diff, cur, next=-1;
5 if(cur_routes>MAX_ROUTES || cur_routes>=min)
6 return;
7 if(begin == -1) {
8 min = cur_routes;
9 return;
10 }
11 --tm[begin];
12 cur = begin;
13 for(i=cur+1; i<MAX_T; i++) {
14 if(tm[i]) {
15 diff = i - begin;
16 /* check */
17 for(j=i; j<MAX_T; j+=diff)
18 if(!tm[j])
19 break;
20 if(j<MAX_T)
21 continue;
22
23 for(j=i; tm[j]&&j<MAX_T; j+=diff)
24 --tm[j];
25 for(k=begin+1; k<MAX_T/2; k++)
26 if(tm[k] && next==-1)
27 next = k;
28 dfs(next, cur_routes+1);
29 for(j=i; j<MAX_T; j+=diff)
30 ++tm[j];
31 cur = i;
32 }
33 }
34 ++tm[begin];
35 }
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_R 910
5 #define MAX_T 60
6 #define MAX_RT 17
7 struct Route {
8 int begin;
9 int interval;
10 int stops;
11 } routes[MAX_R];
12 int cnt, left, n, min, tm[MAX_T];
13
14 int
15 compare(const void *arg1, const void *arg2)
16 {
17 return ((struct Route *)arg2)->stops - ((struct Route *)arg1)->stops;
18 }
19
20 int
21 check(int begin, int interval)
22 {
23 int i;
24 for(i=begin; i<MAX_T; i+=interval)
25 if(!tm[i])
26 return 0;
27 return 1;
28 }
29
30 void
31 init()
32 {
33 int i, j, tmp;
34 min = MAX_RT + 1;
35 cnt = 0;
36 left = n;
37 memset(tm, 0, sizeof(tm));
38 for(i=0; i<n; i++) {
39 scanf("%d", &tmp);
40 ++tm[tmp];
41 }
42 for(i=0; i<29; i++) { /* 0<=begin<=29 */
43 if(tm[i]) {
44 for(j=i+1; j<59-i; j++)
45 if(check(i, j)) {
46 routes[cnt].begin = i;
47 routes[cnt].interval = j;
48 routes[cnt++].stops = 1 + (59-i)/j;
49 }
50 }
51 }
52 qsort(routes, cnt, sizeof(struct Route), compare); /* descend order */
53 }
54
55 void
56 dfs(int index, int r_cnt)
57 {
58 int i, k, j;
59 if(left == 0) {
60 min = min<r_cnt ? min : r_cnt;
61 return;
62 }
63 for(i=index; i<cnt&&routes[i].stops>left; i++);
64 for(k=i; k<cnt; k++) {
65 /* important pruning */
66 if(r_cnt+1+(left-routes[k].stops)/routes[k].stops >= min)
67 return;
68
69 if(check(routes[k].begin, routes[k].interval)) {
70 for(j=routes[k].begin; j<MAX_T; j+=routes[k].interval) {
71 --tm[j];
72 --left;
73 }
74 dfs(k, r_cnt+1);
75 for(j=routes[k].begin; j<MAX_T; j+=routes[k].interval) {
76 ++tm[j];
77 ++left;
78 }
79 }
80 }
81 }
82
83 int
84 main(int argc, char **argv)
85 {
86 while(scanf("%d", &n) != EOF) {
87 init();
88 dfs(0, 0);
89 printf("%d\n", min);
90 }
91 }