算法
(DFS,迭代加深,剪枝) $O(C_{C_{60}^2}^{17})$
首先预处理出所有可能的线路。先枚举起点i
,再枚举公差j
,则i
和j
需要满足两个条件:
- 由于
i
是起点,因此0 ~ i - 1
中不能包含任何该序列的点,所以公差j
至少是i + 1
; - 由于
0 ~ 59
之间至少要包含两个点,因此i + j
一定小于60;
剩下的问题变成:
最少从合法线路中选出多少条,才可以覆盖所有给定的公交车。
由于总路线数量较多,最多从中选出17条,但实现我们并不知道该选多少条,因此可以采用迭代加深搜索。
剪枝:
- 由于是枚举组合数,并不是排列数,为了避免重复在DFS时传入当前枚举的起点。
- 将所有等差数列按长度排序,优先枚举长度较长的等差数列。这样在搜索树中前几层的分支少,可以更快地发现矛盾然后回溯。
- 由于剪枝2的存在,当前路线覆盖的点数是最多的,如果当前路线能覆盖的点数 * 剩余可选的路径条数 + 当前已经覆盖的点数 < 总点数,说明当前方案一定非法,直接回溯即可。
时间复杂度
最多有 $C_{60}^2$ 条合法路线,要从这些路线中最多选出 $17$ 条,因此总时间复杂度是 $O(C_{C_{60}^2}^{17})$。
不过由于剪枝的存在,实际搜索到的状态数量很少。
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 2000, M = 60;
int n;
vector<pair<int, PII>> routes;
int bus[M];
bool is_route(int a, int d)
{
for (int i = a; i < 60; i += d)
if (!bus[i])
return false;
return true;
}
bool dfs(int depth, int u, int sum, int start)
{
if (u == depth) return sum == n;
if (routes[start].first * (depth - u) + sum < n) return false;
for (int i = start; i < routes.size(); i ++ )
{
auto r = routes[i];
int a = r.second.first, d = r.second.second;
if (!is_route(a, d)) continue;
for (int j = a; j < 60; j += d) bus[j] -- ;
if (dfs(depth, u + 1, sum + r.first, i)) return true;
for (int j = a; j < 60; j += d) bus[j] ++ ;
}
return false;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
int t;
scanf("%d", &t);
bus[t] ++ ;
}
for (int i = 0; i < 60; i ++ )
for (int j = i + 1; i + j < 60; j ++ )
if (is_route(i, j))
routes.push_back({(59 - i) / j + 1, {i, j}});
sort(routes.begin(), routes.end(), greater<pair<int, PII>>());
int depth = 0;
while (!dfs(depth, 0, 0, 0)) depth ++ ;
printf("%d\n", depth);
return 0;
}
想问一下 用bfs怎么写啊
#include[HTML_REMOVED]
using namespace std;
int cnt,n,a[310],t[70];
vector[HTML_REMOVED] > > route;
bool check(int a1,int d) {
for(int i=a1; i<60; i+=d) {
if(!t[i])return false;
}
return true;
}
static bool cmp(const pair[HTML_REMOVED] >& a, const pair[HTML_REMOVED] >& b) {
return a.first > b.first;
}
bool dfs(int depth,int step,int sum,int now) {
if(step==depth+1)return sum==n;
if(sum+route[now].first(depth-step+1)[HTML_REMOVED]>n;
for(int i=1; i<=n; i) {
cin>>a[i];
t[a[i]];
}
for(int i=1; i<=n; i) {
for(int d=a[i]+1; a[i]+d<60; d) {
if(check(a[i],d)) {
route.push_back(make_pair((59-a[i])/d+1,make_pair(a[i],d)));
//cout<<a[i]<<’ ‘<<d<<’ ‘<<(59-a[i])/d+1<<endl;
}
}
}
sort(route.begin(),route.end(),cmp);
int depth=1;
while(!dfs(depth,1,0,0))depth;
cout<<depth;
/*for(int i=0;i<route.size();i){
cout<<route[i].first<<’ ‘<<route[i].second.first<<’ ‘<<route[i].second.second<<endl;
}/
//cout<<route.size();
return 0;
}
为什么超时
高,实在是高,特别是这个dfs函数的设计,这几个数值取值有点迷-_-! 咋个算都没算明白,但又是对的。。
预处理妙啊
老哥,我想问一下 为什么 dfs中还要 if (!is_route(a, d)) continue;, main函数中不是check过了
n个时间,第i个时间只能用一次,如果你这条线路用了第i个时间,那么第i个时间就已经被占用了,然后以后的线路就不能再用第i个时间了。(讲的不明白,多多包涵QAQ)
对滴。
yls
我觉得您的代码跑不了这组数据吧:
8
0 0 3 3 6 6 9 9
数据不合法,没有给出每条线路上所有汽车到达的时刻。
效率为啥不高啊! ?
大师,请问为啥不可以依次考虑每一个时间作为线路起点,然后标记枚举? ?
优先枚举覆盖点数较多的路线分支会更少,迭代加深的时候更容易提前剪枝。如果先枚举起点再枚举终点就不能保证优先枚举覆盖点数较多的路线了。
理解错题意气死人诶
呜呜呜 ~~~ %>_<%
加油hh
我以为是像 $3$ $6$ $9$ $12$ 这一条线路也是合法的(没有到 $60$),,,
所以每条巴士线路是一条完整的等差数列??
对滴。
大佬,剪枝该怎么学啊?QAQ
多刷题,积累经验~
我写了个小猫爬山的模型然后TLE了qwq
这题的搜索空间比较大,需要多加一些剪枝。