一、通过利用预处理降低时间复杂度（6/6）

题目解析

首先预处理出所有可能的线路。先枚举起点i，再枚举公差j，则i和j需要满足两个条件：
1.由于i是起点，因此0 ~ i - 1中不能包含任何该序列的点，所以公差j至少是i + 1；
2.由于0 ~ 59之间至少要包含两个点，因此i + j一定小于60；

剩下的问题变成：
最少从合法线路中选出多少条，才可以覆盖所有给定的公交车。

由于总路线数量较多，最多从中选出17条，但实现我们并不知道该选多少条，因此可以采用迭代加深搜索。
剪枝：
1.由于是枚举组合数，并不是排列数，为了避免重复在DFS时传入当前枚举的起点。
2.将所有等差数列按长度排序，优先枚举长度较长的等差数列。这样在搜索树中前几层的分支少，可以更快地发现矛盾然后回溯。
3.由于剪枝2的存在，当前路线覆盖的点数是最多的，如果当前路线能覆盖的点数 * 剩余可选的路径条数 + 当前已经覆盖的点数 < 总点数，说明当前方案一定非法，直接回溯即可。

注意：
1.剪枝操作在下面的代码中也有详细的说明
2.这里迭代加深使用的参数depth，名义上表示是在限制树的深度，实际上是在限制最多可以被纳入到答案线路的合法线路数量。

关于迭代加深的小总结：
1.depth明面上都是表示限制搜索过程中最多可到的树的深度，实际上是有实际含义的，又专门的限制意义，限制某个数据量不能超过多少多少，这个数据量通常是dfs函数中的参数，是会随着dfs的迭代而发生变化的。
2.迭代加深算法中dfs函数的返回值通常是一个bool类型，当搜到答案结点时会通过不断向上层返回true，而不断向上层回溯，直到返回到主函数。
3.迭代加深算法在main主函数中基本格式如下：

int depth = 0;
    while(!dfs(depth, 0, 0, 0)) depth ++;

代码展示

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
int bus[65];//b[i]记录第i时刻有多少辆巴士到达 
vector<pair<int, PII>> q;//q用来存储所有合法序列的信息(项数，首项，公差) 
int n;
bool is_ok(int a0, int d)
{
    for(int i = a0; i < 60; i += d)
    {
        if(bus[i] == 0) return false;
    }
    return true;
}
//u来记录正在计划确定的是答案线路中的第几条线路，即在合法线路中，哪一条合法线路可以作为答案线路。 
//sum是用来记录在已经确定的线路中，有多少巴士被覆盖。 
bool dfs(int depth, int start, int u, int sum)
{
    if(u == depth) return sum == n;
    //如果从当前剩余的所有合法线路中选择出可以覆盖巴士数量num最多的那个
    //（之前已经对所有线路按可覆盖巴士数量从大到小排了序），
    //取num与剩余合法路线数的乘积， 
    //再加上之前已覆盖的车站数量，如果计算结果仍不能达到要求的总数量，
    //说明当前方案不合法，可以直接返回上一层。 
    if(q[start].first * (depth - u) + sum < n) return false;
    //枚举所有的合法路线 
    for(int i = start; i < q.size(); i ++)
    {
        auto t = q[i];
        auto t0 = t.second;
        int num = t.first, a0 = t0.first, d = t0.second;
        //if语句判断q[i]路径是否还合法： 
        //因为之前已经选择了一些合法线路作为答案线路，这会导致一些巴士已经被覆盖掉，
        //而一个巴士只能被覆盖一次（注意，这里的一个巴士就是指一个巴士，而不是在同一
        //时刻到达的所有巴士），因此我们需要重新判断q[i]这条线路上各个时刻的巴士数量
        //是否出现某一时刻没有一辆巴士的情况，如果出现，说明该条线路已经不再合法，如
        //果执意要选这条线路，则会导致某一巴士被重复覆盖。 
        if(is_ok(a0, d) == 0) continue;
        //将bus[]数组记录的数据认作是还未被覆盖的巴士
        //下面这一行循环枚举的是将该合法路线上的巴士都从未被覆盖巴士的名单上删除 
        for(int j = a0; j < 60; j += d) bus[j] --; 
        //因为每一个巴士不会被重复覆盖，所以直接sum+num即可
        //因为某一线路上某个时刻可以覆盖多辆巴士，因此在下一次枚举的时候依然从该条线路
        //（即第i条线路）开始枚举，而不是第i + 1条 
        if(dfs(depth, i, u + 1, sum + num)) return true;
        //恢复现场 
        for(int j = a0; j < 60; j += d) bus[j] ++; 
    }
    return false; 
}
int main()
{
    cin >> n;
    //这里一定不能用while(n --)，因为 n-- 等价于 n = n - 1，会改变 n的值，
    //而我们在接下来的代码中依然会用到 n，因此不能改变 n的值
    //呜呜呜，被这个东西硬控了快两个小时 T..T 
    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; j + i < 60; j ++)//枚举公差 
        {
            if(is_ok(i, j))//判断以i为首项，j为公差的序列可以成为一个路线 
                q.push_back( {  (59 - i)/j + 1,  {i, j}  } );
        }
    }
    //通过以上的操作我们得到了所有可能出现的合法路线，现在我们的任务就是从这些合法路线中，
    //尽可能少的选择一些路线将所有巴士覆盖。

    //我们发现一些选取合法的过程实际上是组合型枚举的过程，因此我们可以采取组合型枚举的方
    //式去遍历所有的路线选取方案。

    //我们又可以通过贪心的思想发现，为了选取更少的线路对所有巴士进行覆盖，我们可以先枚举
    //含有元素较多的路线，即在进行dfs之前，我们可以对初始化的所有合法路线进行一个排序，将
    //元素多的路线放在前面。（剪枝——优化搜索顺序，优先搜索分枝较少的路径）
    sort(q.begin(), q.end(), greater<pair<int, PII>>()); 
    int depth = 0;
    while(!dfs(depth, 0, 0, 0)) depth ++;
    cout << depth << endl; 
    return 0;
} 

二、仅仅使用了迭代加深（4/6）

代码展示

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 310;
int a[N];
int b[20];//记录每一条线路多久发一次车 ，编号与q数组对应 
vector<int> q[20];//记录每一个分组中的元素 
int n;
//u表示正在处理的是哪一个元素，v表示已经有了多少分组 
bool dfs(int depth, int u, int v)
{
    if(v >= depth) return false; 
    if(u >= n)
    {
        for(int i = 0; i < v; i ++)
        {
            if(q[i].size() <= 1) return false;
        }
        return true;
    }
    //遍历已存在的分组，看看u元素可不可以放入 
    for(int i = 0; i < v; i ++)
    {
        if(b[i] == -1)//该线路中只有一辆车
        {
            b[i] = a[u] - q[i].back();
            q[i].push_back(a[u]);
            if(dfs(depth, u + 1, v)) return true;
            else
            {
                q[i].pop_back();
                b[i] = -1;  
            }
        }
        else
        {
            if(a[u] - q[i].back() != b[i]) continue;
            q[i].push_back(a[u]);
            if(dfs(depth, u + 1, v)) return true;
            else q[i].pop_back();
        }
    }
    //如果没有可以放入的分组，那么就新开一个分组
    if(v + 1 > depth) return false;
    q[v].push_back(a[u]);
    if(dfs(depth, u + 1, v + 1)) return true;
    else q[v].clear();
    return false;
}
int main()
{
    memset(b, -1, sizeof b);
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);
    int depth = 1;
    while(!dfs(depth, 0, 0)) depth ++;
    cout << depth - 1 << endl;
    return 0;
}