IOI1994 汽车问题

题目:

   有一个人在某个公共汽车站上,从12:00到12:59观察公共汽车到达本站的情况,该站被多条公共汽车线路所公用,他依次记下公共汽车到达本站的时刻。
   在12:00-12:59期间,同一条线路上的公共汽车以相同的时间间隔到站。
   时间单位用“分”表示,从0到59 。
   每条公共汽车线路至少有两辆车到达本站。
   公共汽车线路数K一定≤17,汽车数目N一定小于300。
   来自不同线路的公共汽车可能在同一时刻到达本站。
   不同公共汽车线路的车首次到站时间和到站的时间间隔都有可能相同。
   请为公共汽车线路编一个调度表,目标是:公共汽车线路数目最少的情况下,使公共汽车到达本站的时刻满足输入数据的要求。

思路:

   第一反应是把当前第一个没被选择的汽车作为一条线路的开头,再枚举第二个汽车来确定出一条路径。但是这样每层能枚举出的路线数量是左右的,直接TLE。再考虑按照时间枚举,这样每层的情况数是,虽然比之前快了很多,但是还是会T。
   考虑到路线数一定,那么可以试着让每层的枚举量也是这个数。把所有作为路线开头的汽车存下来,每次把当前搜到的汽车作为第二辆来确定一条路线。这样的枚举量就只有,在加上最优性剪枝,跑得飞快。

代码:

#include <bits/stdc++.h>
#define debug(x) std::cerr<<"DEBUG:"<<#x<<'='<<(x)<<std::endl
#define rep(i,a,b) for(int i=(a),i##_END_=(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i=(a),i##_END_=(b);i>=i##_END_;i--)
#define dotimes(k) for(int _##__LINE__##_=(k);_##__LINE__##_>=1;_##__LINE__##_--)
const int MN=305;
int t[MN],vec[MN],stk[MN],top;
bool used[MN],mark[MN];
int ans=17,n,max;
void dfs(int o,int now){
#define push(x) (stk[++top]=(x))
#define pop() stk[top--]
    if(now>=ans)return;
    if(o==n+1){
        rep(i,1,now){
            if(!mark[vec[i]])
                return;
        }
        return (void)(ans=now);
    }
    if(used[o])return dfs(o+1,now);
    rep(i,1,now){
        if(mark[vec[i]])continue;
        int d=t[o]-t[vec[i]],las=t[o],tmp=top;
        used[o]=true;
        push(o);
        rep(j,o+1,n){
            if(used[j])continue;
            if(t[j]-las<d)continue;
            if(t[j]-las>d)break;
            used[j]=true;
            push(j);
            las=t[j];
        }
        mark[vec[i]]=true;
        if(las+d>max)dfs(o+1,now);
        mark[vec[i]]=false;
        while(top>tmp)
            used[pop()]=false;
    }
    vec[now+1]=o;
    used[o]=true;
    dfs(o+1,now+1);
    used[o]=false;
#undef push
#undef pop
}
int main(){
//  freopen("data.in","r",stdin);
    scanf("%d",&n);
    rep(i,1,n)
        scanf("%d",t+i);
    std::sort(t+1,t+1+n);
    max=t[n];
    dfs(1,0);
    printf("%d\n",ans);
    return 0;
}