题解 P1499 【公路巡逻】

· · 题解

具体看注释！！！

具体看注释！！！

具体看注释！！！

步骤：

**1. 看代码

  1. 看代码

  2. 看代码**

//不加注释的题解都是流氓
#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;//start：出发时刻，end：到达时刻
} car[305][305];//car[i][j]：从i关口出发的第j辆车
int n,m;
int dp[55][33000]={0};//dp[i][j]：到达第i个关口耗时j秒遇到巡逻车的最小次数
int num[305]={0};//num[i]:从第i个关口出发的巡逻车数
int change(int time)//传入hhmmss格式的时间，返回从6点开始到这个时刻的秒数
{
    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)//传入6点开始到现在的秒数，返回hhmmss格式的时间数字（不含前导0）
{
    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()
{
    freopen("patrol.in","r",stdin);
    freopen("patrol.out","w",stdout);
    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--;//因为数组从0开始
        Ti=change(Ti);
        car[ni][num[ni]].start=Ti;
        car[ni][num[ni]].end=ti+Ti;
        num[ni]++;
    }
    dp[0][0]=0;
    n--;//因数组从0开始
    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);//dp方程
                if (dp[i+1][jk]==0) {//优化：dp[i][j]=0,则dp[i][k](k>j)皆为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");//补前导0
    printf("%d\n",printTime);
    return 0;
}