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