The Buses （poj 1167 搜索）

Language: Default The Buses Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5809 Accepted: 1606 Description A man arrives at a bus stop at 12:00. He remains there during 12:00-12:59. The bus stop is used by a number of bus routes. The man notes the times of arriving buses. The times when buses arrive are given.  Buses on the same route arrive at regular intervals from 12:00 to 12:59 throughout the entire hour.  Times are given in whole minutes from 0 to 59.  Each bus route stops at least 2 times.  The number of bus routes in the test examples will be <=17.  Buses from different routes may arrive at the same time.  Several bus routes can have the same time of first arrival and/or time interval. If two bus routes have the same starting time and interval, they are distinct and are both to be presented. Find the schedule with the fewest number of bus routes that must stop at the bus stop to satisfy the input data. For each bus route, output the starting time and the interval.  Input Your program is to read from standard input. The input contains a number n (n <= 300) telling how many arriving buses have been noted, followed by the arrival times in ascending order. Output Your program is to write to standard output. The output contains one integer, which is the fewest number of bus routes. Sample Input 17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53 Sample Output 3 Source IOI 1994

题意：给出n个时刻，这n个时刻有车到站，问最少要多少条路线可以满足输入。每条路线在0~59之间至少要停两站，到站之间的时间间隔是相等的。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b)  for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define DBG         pf("Hi\n")
typedef long long ll;
using namespace std;

struct Route
{
    int start,p,time;
}route[maxn];

int n,arr[65];
int route_num;  //可能路线的总数
int Left;  //剩下的还没有使用的到站时刻点数
int Min;  //最终答案

int cmp(Route a,Route b)
{
    return a.time>b.time;
}

bool isok(int s,int p)     //判断第一次进站时间为s，间隔为p的路线是否符合条件
{
    if (s+p>59) return false;  //期间只有一次到站的路线不符合条件
    for (int i=s;i<60;i+=p)
    {
        if (!arr[i])
            return false;
    }
    return true;
}

void dfs(int r,int ans)
{
    if (Left==0)
    {
        if (ans<Min)    //更新答案
            Min=ans;
        return ;
    }
    int temp=r;
    while (temp<route_num&&route[temp].time>Left) temp++;
    while (temp<route_num&&ans+1+(Left-route[temp].time)/route[temp].time<Min)
    {
        if (isok(route[temp].start,route[temp].p))  //判断是否满足基本条件
        {
            for (int i=route[temp].start;i<60;i+=route[temp].p)
            {
                arr[i]--;
                Left--;
            }
            dfs(temp,ans+1);
            for (int i=route[temp].start;i<60;i+=route[temp].p) //回溯
            {
                arr[i]++;
                Left++;
            }
        }
        temp++;
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("C:/Users/asus1/Desktop/IN.txt","r",stdin);
#endif
    int i,j;
    while (~sf(n))
    {
        int x;
        memset(arr,0,sizeof(arr));
        route_num=0;
        Min=17;
        Left=n;
        FRL(i,0,n)
        {
            sf(x);
            arr[x]++;
        }
        //第一次到达的时间start<p   ----（1）
        //两次到达之间的间隔满足start<=59-p    ----（2）
        //由（1）（2）得start<=29
        for (i=0;i<=29;i++)     //i枚举start，j枚举p
        {                       //预处理出所有可能的路线
            if (arr[i])
            for (j=i+1;j<=59-i;j++)
            {
                if (isok(i,j))
                {
                    route[route_num].start=i;
                    route[route_num].p=j;
                    route[route_num++].time=1+(59-i)/j;
                }
            }
        }
        //为了尽快找到一个小的当前最优解，那么希望每次尝试一个路线就能砍掉尽量多的到站时刻
        sort(route,route+route_num,cmp);        //因此按照每条路线在0~59之间到的到站次数从大到小排序
        dfs(0,0);
        pf("%d\n",Min);
    }
    return 0;
}
/*
17
0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53
*/
           

Language: Default The Buses Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5809 Accepted: 1606 Description A man arrives at a bus stop at 12:00. He remains there during 12:00-12:59. The bus stop is used by a number of bus routes. The man notes the times of arriving buses. The times when buses arrive are given.  Buses on the same route arrive at regular intervals from 12:00 to 12:59 throughout the entire hour.  Times are given in whole minutes from 0 to 59.  Each bus route stops at least 2 times.  The number of bus routes in the test examples will be <=17.  Buses from different routes may arrive at the same time.  Several bus routes can have the same time of first arrival and/or time interval. If two bus routes have the same starting time and interval, they are distinct and are both to be presented. Find the schedule with the fewest number of bus routes that must stop at the bus stop to satisfy the input data. For each bus route, output the starting time and the interval.  Input Your program is to read from standard input. The input contains a number n (n <= 300) telling how many arriving buses have been noted, followed by the arrival times in ascending order. Output Your program is to write to standard output. The output contains one integer, which is the fewest number of bus routes. Sample Input 17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53 Sample Output 3 Source IOI 1994