考察:搜索
思路:
这道题题目描述略坑,这里简述下题意:
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 }
原文：https://www.cnblogs.com/newblg/p/14702141.html