CF1415F 题解

First Post:

Last Update:

遇到新题型，茫然无措是必然的，但只有冷静下来，运用自己掌握的思维模式，才能从茫然中找到柳暗花明。

考虑已经确定了本体和分身完成的任务集合，怎么判定合法性。

设本体完成的任务为 A 类，分身完成的任务为 B 类。

把 看成二维平面上的点，容易绘制以下图像：

我们的行动轨迹需要经过上图所有的点。

A 类任务可以限制人的行动轨迹，相比 B 类任务具有更加”稳定“的约束，我们考虑研究两个 A 任务之间的间隔。

右图是两个 A 夹着一段极长的 B ，左图是一段极长的 A。

蓝色是不管 B 的路线，红色是管 B 的路线。

容易发现，一段极长的 A，只会贡献一个 B，一段极长的 B 的非开头部分 只会由夹着这一段的两个 A 解决（开头那个被绿色圈住的部分可能已经被前一段解决）

（上述图片来自 @command_block，感谢 cmd 的题解）

两个 A 之间的间隔，就是一段 B 的极长连续段。

假设这些 任务按时间顺序为 ， 对应的时间区间为 ，其实就是 。

设初始时间为 ，初始位置为 ，假设下一个任务为 ，那么如果 ，则方案不合法，否则 变为 ， 也对应变化（对 取 是因为，假如我在 之前就到达了 ，我也必须等到 的时候才能撤销原本放在那里的分身，把它移到当前位置）

观察上述的贪心算法，我们只需在 的时候维护上面的 ，然后一个一个加入 B 类任务即可。

具体地，设 表示任务 是 B 类，任务 是/否已经被 之前的某一段 A 解决。（也就是那个绿色圈的情况）

对于 ，当前本体肯定在 ，对于 ， 是 A 类，并且本体在 。

记 表示任务 是否能成为一段 A。

记 。

对于 :

  • 是 B 类

    1. 从 转移：
    2. 从 转移：

  • 是 A 类

    枚举 A 类极长连续段 。

    条件：

    为真

    且 （ 可以走到 ）

    且 （可以从 走到 ）

对于 ：

条件：

枚举 A 类极长连续段 。

存在一个 满足：

  • 为真

  • 且 （ 可以走到 ）

  • 且存在一个 （存在一个空隙使得人可以拐出来，先放好分身再走回去） 或者 （这一段 A 的开头和上一段 B 的结尾之间有个空隙可以让人出来放分身）

把转移都分讨完后，代码就比较简单了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 5;
int n;
struct node {ll x,t;} p[N];
bool cmp(const node &a,const node &b) { return a.t < b.t;}
ll dis(int x,int y) { return abs(p[x].x - p[y].x);}

ll f[N][2];
bool g[N];
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> p[i].t >> p[i].x;
	p[++n].t = 0;p[n].x = 0;
	p[++n].t = llinf - 1;p[n].x = 0;
	sort(p + 1,p + n + 1,cmp);
	f[1][1] = llinf;
	for(int i = 2;i <= n;i++)
	{
		g[i - 1] = dis(i - 1,i) <= p[i].t - p[i - 1].t;
		f[i][0] = f[i][1] = llinf;
		ll now = f[i - 1][0] + dis(i - 1,i);
		if(now <= p[i].t) f[i][0] = min(f[i][0],max(now,p[i - 1].t));
		now = f[i - 1][1] + dis(i - 2,i);
		if(now <= p[i].t) f[i][0] = min(f[i][0],max(now,p[i - 1].t));
		bool flag = 0;
		for(int j = i - 2;j >= 1;j--) // 枚举 A 类极长连续段 [j + 1,i - 1]
		{
			if(j + 2 < i)
			{
				if(!g[j + 1]) break;
				flag |= (dis(i,j + 1) + dis(i,j + 2) <= p[j + 2].t - p[j + 1].t);
			}
			// B 类 j 要接上 A 类 j + 1
			if(min(f[j][0] + dis(j,j + 1),f[j][1] + dis(j - 1,j + 1)) <= p[j + 1].t)
			{
				if(flag || max(min(f[j][1] + dis(j - 1,i),f[j][0] + dis(j,i)),p[j].t) + dis(i,j + 1) <= p[j + 1].t)
					f[i][1] = p[i - 1].t;
				if(g[i - 1]) f[i][0] = min(f[i][0],p[i - 1].t + dis(i - 1,i));
			}
		}
	}
	if(min(f[n][0],f[n][1]) < llinf) puts("YES");
	else puts("NO");
	return 0;
}

总的来说，是一道比较复杂的 DP 题，非常具有 CF 风格，虽然最后的转移情况很多，但并没有思维上的难度，真正的难点主要在前面的状态设计和对问题的刻画。注意到 A 类和 B 类各自的贡献条件是十分重要的，这样才能开始后面的转化。

愈是复杂，愈要冷静。

≡