POJ - 1167 The Buses（DFS,迭代加深,剪枝）_综合

POJ - 1167 The Buses

(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})$
不过由于剪枝的存在，实际搜索到的状态数量很少。

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N = 2000, M = 60;
int n;
vector<PIII> routes;
int bus[M];
bool check(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<(int)routes.size();i++){
    PIII r=routes[i];int a=r.second.first, d=r.second.second;if(!check(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 a=0;a<30;a++)for(int b=a+1;a+b<60;b++)if(check(a,b))routes.push_back((PIII){
    (59-a)/b+1,(PII){
    a,b}});sort(routes.begin(),routes.end());reverse(routes.begin(),routes.end());int depth=0;while(!dfs(depth,0,0,0)) depth++;printf("%d\n",depth);return 0;
}