专栏文章

题解：P1499 [CTSC2000] 公路巡逻

llinjinkun
P1499题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjpqpy
此快照首次捕获于
2025/12/02 03:32
3 个月前
此快照最后确认于
2025/12/02 03:32
3 个月前
查看原文
中等难度 DP。
首先为了方便先将时间转换成秒。
设 fi,jf_{i,j} 表示在 jj 时间到达关口 ii 最少遇到的巡逻车数量。
转移显然： fi,j=max⁡{fi−1,j−k+q(i−1,j−k,j)}f_{i,j} = \max\{f_{i-1,j-k}+q(i-1,j-k,j)\} 其中 q(a,b,c)q(a,b,c) 表示在 bb 时间从 aa 关口到 a+1a+1 关口此时正好在 cc 时间会遇到的巡逻车数量，那么重点是如何实现这个函数？其实很简单，对于每一辆巡逻车（必须和我们这辆车的出发点相同）分三种情况才会相遇：
  1. 如果我们这辆车与第 ii 辆巡逻车的重点相同。
  2. 如果我们比第 ii 辆巡逻车出发得早但到得比它晚。
  3. 如果我们比第 ii 辆巡逻车出发得晚却到得比它早。
kk 的取值也很显然，毕竟每个关口距离都是 1010 千米，然后速度又有范围，直接算即可。
代码（看完代码别划走，还有附录）：
CPP
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define FASTIO
#define IOSIZE 100000
	char ibuf[IOSIZE], obuf[IOSIZE];
	char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local

#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() {
		T s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
		if (ch == EOF) return false;
		while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
		return s * w;
	}
	template<typename T> inline bool read(T &s) {
		s = 0;
		int w = 1;
		char ch;
		while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
		if (ch == EOF) return false;
		while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
		return s *= w, true;
	}
	inline bool read(char &s) {
		while (s = getchar(), isspace(s));
		return true;
	}
	inline bool read(char *s) {
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF) return false;
		while (!isspace(ch)) *s++ = ch, ch = getchar();
		*s = '\000';
		return true;
	}
	template<typename T> inline void print(T x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x % 10 + 48);
	}
	inline void print(char x) {
		putchar(x);
	}
	inline void print(char *x) {
		while (*x) putchar(*x++);
	}
	inline void print(const char *x) {
		for (int i = 0; x[i]; ++i) putchar(x[i]);
	}
	inline bool read(std::string& s) {
		s = "";
		char ch;
		while (ch = getchar(), isspace(ch));
		if (ch == EOF) return false;
		while (!isspace(ch)) s += ch, ch = getchar();
		return true;
	}
	inline void print(std::string x) {
		for (int i = 0, n = x.size(); i < n; ++i)
			putchar(x[i]);
	}
	template<typename T, typename... T1> inline int read(T& a, T1&... other) {
		return read(a) + read(other...);
	}
	template<typename T, typename... T1> inline void print(T a, T1... other) {
		print(a);
		print(other...);
	}

	struct Fast_IO {
		~Fast_IO() {
			fwrite(obuf, p3 - obuf, 1, stdout);
		}
	} io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) {
		return read(b), io;
	}
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) {
		return print(b), io;
	}
#define cout io
#define cin io
#define endl '\n'
}
using namespace fast_IO;
int st[55][305],ed[55][305];
int f[55][30005];
inline int chuli(int x)
{
    return (x/10000-6)*3600+(x%10000/100)*60+x%100;
}
inline int zhuanyi(int x,int stt,int edd)
{
    int ans = 0;
    for(int i = 1;i<=st[x][0];++i)
    {
        if(edd == ed[x][i])
        {
            ++ans;
        }
        else if(st[x][i]<stt&&edd<ed[x][i])
        {
            ++ans;
        }
        else if(st[x][i]>stt&&edd>ed[x][i])
        {
            ++ans;
        }
    }
    return ans;
}
signed main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=m;++i)
    {
        int x,y,z;
        cin >> x >> y >> z;
        y = chuli(y);
        ++st[x][0];
        st[x][st[x][0]] = y;
        ed[x][st[x][0]] = y+z;
	}
    memset(f,0x3f,sizeof(f));
    f[1][0] = 0;
    for(int i = 2;i<=n;++i)
    {
        int l = (i-1)*300,r = (i-1)*600;
        for(int j = l;j<=r;++j)
        {
            for(int k = 300;k<=600;++k)
            {
                f[i][j] = min(f[i][j],f[i-1][j-k]+zhuanyi(i-1,j-k,j));
            }
        }
    }
    int minn = 2e9,ans = 0;
    int l = (n-1)*300,r = (n-1)*600;
    for(int i = l;i<=r;++i)
    {
        if(f[n][i]<minn)
        {
            minn = f[n][i];
            ans = i;
        }
    }
    printf("%d\n%06d",minn,(ans/3600+6)*10000+ans%3600/60*100+ans%60);
    return 0;
}
附录：
时间复杂度？三层循环加一个看起来 O(n)O(n) 的函数，你可能会以为超时了，实则不然，因为你会发现这个函数可以均摊（真的可以吗，其实我也不知道），复杂度最最最最最最最坏就大约是（其实根本达不到）： n×∑i=2n300×(i−1)×300n \times \sum_{i = 2}^n 300 \times (i-1) \times 300 =n×∑i=2n90000×(i−1)=n \times \sum_{i = 2}^n 90000 \times (i-1) 拿程序跑一遍，你会发现这个式子最坏情况是 12175327041217532704，咦？1.2×1091.2 \times 10^9 难道不是超时了，其实前面说了，这只是粗略估算，我们再次细致估算一下，首先对于这个看似均摊的东西，很显然将所有巡逻车设成同一个出生点即可让时间最慢，你就会发现，这样精美的构造就算在粗略估算（实则根本跑不到）的情况下也就才 432180000‬432180000‬，很显然在一秒内轻松通过。
所以评测机才如此轻松。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...