/ Vijos / 题库 / 公路巡逻 /

题解

15 条题解

  • 0
    @ 2016-08-22 16:56:00 
    #include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <fstream>
using namespace std;
const int INF=66666666;
struct node {
    int start,end;
} car[305][305];
int n,m;
int dp[55][33000]={0};
int num[305]={0};
int change(int time)
{
    int h,m,s;
    h=time/10000;
    time-=h*10000;
    h-=6;
    m=time/100;
    time-=m*100;
    s=time;
    return (h*3600+m*60+s);
}
int changeBack(int T)
{
    int h,m,s;
    h=T/3600;
    T-=h*3600;
    h+=6;
    m=T/60;
    T-=m*60;
    s=T;
    return h*10000+m*100+s;
}
int main()
{
    scanf("%d %d",&n,&m);
    int n600=n*600;
    int ni,Ti,ti;
    memset(dp,50,sizeof(dp));
    for(int i=0; i<m; i++) {
        scanf("%d %d %d",&ni,&Ti,&ti);
        ni--;
        Ti=change(Ti);
        car[ni][num[ni]].start=Ti;
        car[ni][num[ni]].end=ti+Ti;
        num[ni]++;//ni个站点出发有几辆车
    }
    dp[0][0]=0;
    n--;
    bool b=false;
    for(int i=0; i<n; i++) {
        for(int j=i*300,i600=i*600; j<=i600; j++) {
            for(int k=300; k<=600; k++) {
                int times=0,jk=j+k;
                for(int p=0; p<num[i]; p++) {
                    if((car[i][p].start>=j&&car[i][p].end>jk)||(car[i][p].start<=j&&car[i][p].end<jk))
                        continue;//没有超车
                    else
                        times++;//超车或同时到达
                }
                dp[i+1][jk]=min(dp[i+1][jk],dp[i][j]+times);
                if (dp[i+1][jk]==0) {
                    for (int p=jk+1,i602=i600+600;p<=i602;p++) {
                        dp[i+1][p]=0;
                    }   
                    b=true;
                    break;
                }
            }
            if (b) break;
        }
        if (b) {
            b=false;
            continue;
        }
    }
    int result=INF;
    int minTime;
    for(int i=n*300,n601=n600-600; i<=n601; i++) {
        if(result>dp[n][i]) {
            result=dp[n][i];
            minTime=i;
        }
    }
    int printTime=changeBack(minTime);
    printf("%d\n",result);
    if (printTime<100000) printf("0");
    printf("%d\n",printTime);
    return 0;
}
  • 0
    @ 2012-09-06 20:06:51

    貌似是黑书上的例题啊 暂时不会 先放放。。

  • 0
    @ 2009-10-09 20:17:45

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 212ms

    ├ 测试数据 05：答案正确... 197ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 25ms

    ├ 测试数据 09：答案正确... 150ms

    ├ 测试数据 10：答案正确... 369ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：953ms

    sunny 惹得祸

  • 0
    @ 2009-10-08 16:04:06

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 40ms

    ├ 测试数据 04：答案正确... 415ms

    ├ 测试数据 05：答案正确... 352ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 25ms

    ├ 测试数据 08：答案正确... 87ms

    ├ 测试数据 09：答案正确... 259ms

    ├ 测试数据 10：答案正确... 602ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：1780ms

    dragon

    常数优化下 终于过了

  • 0
    @ 2009-10-04 09:37:44

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 56ms

    ├ 测试数据 04：答案正确... 56ms

    ├ 测试数据 05：答案正确... 56ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 119ms

    ├ 测试数据 10：答案正确... 197ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：484ms

    BS一下 VIJOS 201不报错

    害了我半个早上

  • 0
    @ 2009-09-12 10:53:35

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 25ms

    ├ 测试数据 05：答案正确... 9ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 9ms

    ├ 测试数据 10：答案正确... 72ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：115ms

    时间转错了，纠结了半天

  • 0
    @ 2009-01-08 23:45:37

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    就是加一个剪枝，如果d[i][t]==0,那么所有di][k\都付成0，不必再计算

  • 0
    @ 2008-12-08 12:33:55

    终于AC了，纪念一下。

  • 0
    @ 2008-10-22 17:04:56

    黑书上原题...

  • 0
    @ 2008-10-13 10:54:21

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 9ms

    ├ 测试数据 04：答案正确... 9ms

    ├ 测试数据 05：答案正确... 9ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 41ms

    ├ 测试数据 10：答案正确... 150ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：218ms

    终于AC了。。。

    其实,没必要用lrj那个方法。。。

    只用每次定一个界限，然后如果f=0直接break掉就行了(0是答案的下限)

  • 0
    @ 2008-10-09 11:53:33

    照着黑书上写

    然后优化优化常数

    就过了

    最慢的点700+s

    不知道下面那个RMQ怎么做的......

    注意"假设所有车辆到达关口的时刻都是整秒"

  • 0
    @ 2007-11-12 08:10:32

    第一问是逆序对吧？

  • 0
    @ 2007-09-29 18:27:22

    贪心算法+动态规划+分支定界

  • 0
    @ 2006-11-12 14:27:59

    这题写得……真是天昏地暗

    一开始就想到了lrj书上写的办法，对于最大数据5s

    然后剪枝，对于某个值如果算到0就不再继续算，此时对于最大数据4.5s

    然后……想到用RMQ，写了个Sparse Table，终于ac……

    托puppy的福，最大数据只用了197ms……puppy强啊

  • 0
    @ 2006-07-27 16:18:26

    dp

    令c[x,t]表示在时刻t到达第x个关口最少与巡逻车相遇的次数

    c[x,t]:=min(c[x-1,t-10*k],+f(x-1,t-10*k,t)) (30

  • 1

公路巡逻

信息

ID
1168
难度
5
分类
动态规划 点击显示
标签
递交数
295
已通过
102
通过率
35%
被复制
4
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1