题解：P1499 [CTSC2000] 公路巡逻
linjinkun
·
·
题解
中等难度 DP。
首先为了方便先将时间转换成秒。
设 f_{i,j} 表示在 j 时间到达关口 i 最少遇到的巡逻车数量。
转移显然：
f_{i,j} = \max\{f_{i-1,j-k}+q(i-1,j-k,j)\}
其中 q(a,b,c) 表示在 b 时间从 a 关口到 a+1 关口此时正好在 c 时间会遇到的巡逻车数量，那么重点是如何实现这个函数？其实很简单，对于每一辆巡逻车（必须和我们这辆车的出发点相同）分三种情况才会相遇：
-
如果我们这辆车与第 i 辆巡逻车的重点相同。
-
如果我们比第 i 辆巡逻车出发得早但到得比它晚。
-
如果我们比第 i 辆巡逻车出发得晚却到得比它早。
代码（看完代码别划走，还有附录）：
```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)$ 的函数，你可能会以为超时了，实则不然，~~因为你会发现这个函数可以均摊（真的可以吗，其实我也不知道）~~，复杂度最最最最最最最坏就大约是（其实根本达不到）：
$$n \times \sum_{i = 2}^n 300 \times (i-1) \times 300$$
$$=n \times \sum_{i = 2}^n 90000 \times (i-1)$$
拿程序跑一遍，你会发现这个式子最坏情况是 $1217532704$，咦？$1.2 \times 10^9$ 难道不是超时了，其实前面说了，这只是粗略估算，我们再次细致估算一下，首先对于这个~~看似均摊~~的东西，很显然将所有巡逻车设成同一个出生点即可让时间最慢，你就会发现，这样精美的构造就算在粗略估算（实则根本跑不到）的情况下也就才 $432180000$，很显然在一秒内轻松通过。
所以评测机才如此[轻松](https://www.luogu.com.cn/record/242011649)。