考察:搜索
思路:
这道题题目描述略坑,这里简述下题意:
1.所有路线上的公交车形成等差数列,而且等差数列的最后一项再+d>60.
2.存在两个完全一样的路线.
3.求路线最少值.
由于题目提示信息:ans<=17.可以发现搜索树很深,但是答案在很浅的位置.所以可以用迭代加深搜索.此外这道题很容易想到小猫爬山,但是小猫爬山式解题较难剪枝,只有到最后才能检测是否当前等差数列覆盖了0~59.
这里的思路是预处理所有等差数列,时间复杂度只有60*60.然后统计到达时间到达车的数量.枚举每一条路线直到覆盖所有的车.
当然还需要剪枝:
剪枝1: 组合式枚举路线
剪枝2:优先枚举覆盖点多的路线.
剪枝3:如果当前覆盖数+当前路线允许覆盖数*剩余路线<n return
要注意的是枚举的路线一定要每一项都能覆盖公交车.否则与题意不符.
1 #include <iostream>
2 #include <cstring>
3 #include <vector>
4 #include <algorithm>
5 #include <cstdio>
6 using namespace std;
7 typedef pair<int,int> PII;
8 typedef pair<int,PII> PIII;
9 const int N = 60,M = 3600;
10 int bus[N],n,deep;
11 vector<PIII> road;
12 bool check(int a,int d)
13 {
14 for(int i=a;i<60;i+=d)
15 if(!bus[i]) return 0;
16 return 1;
17 }
18 bool dfs(int cnt,int idx,int sum)
19 {
20 if(!cnt) return sum==n;
21 if(road[idx].first*cnt+sum<n) return 0;//如果当前取最值都不能覆盖直接回溯
22 for(int i=idx;i<road.size();i++)
23 {
24 int sz = road[i].first;
25 int a = road[i].second.first,d = road[i].second.second;
26 if(!check(a,d)) continue;//如果当前队列不能完全覆盖就换一条
27 for(int j=a;j<60;j+=d) bus[j]--;
28 if(dfs(cnt-1,i,sum+sz)) return 1;
29 for(int j=a;j<60;j+=d) bus[j]++;
30 }
31 return 0;
32 }
33 int main()
34 {
35 scanf("%d",&n);
36 for(int i=1;i<=n;i++)
37 {
38 int x;
39 scanf("%d",&x);
40 bus[x]++;
41 }
42 //预处理合法路线,题目要求路线上一定要延续到60
43 for(int a=0;a<60;a++)
44 for(int d =a+1;d+a<60;d++)
45 if(check(a,d)) road.push_back({(59-a+d-1)/d,{a,d}});
46 sort(road.begin(),road.end(),greater<PIII>());
47 while(!dfs(deep,0,0))
48 {
49 deep++;
50 if(deep==17) break;
51 }
52 printf("%d\n",deep);
53 return 0;
54 }