Dyd's Blog

He who has a strong enough why can bear almost any how.

CF1523F Favorite Game

Posted on In
Symbols count in article: 2.3k Reading time ≈ 2 mins.

3300

Favorite Game

题意

在平面直角坐标系 $xoy(\mid x, y \mid \le 10^6)$ 玩一个游戏， $0$ 时刻玩家出现在选则的点上，每秒可以走一步或者不动，有 $n \le 14$ 个传送门，初始时未激活，到达一个传送门时此传送门激活，之后可瞬移（不耗时）到这个传送门，有 $m \le 100$ 个任务要求玩家在 $t_i \le 10^9$ 时刻出现在 $(x_i, y_i)$ ，求最多可以完成几个任务

做题

明显，把传送门的状态压了，任务先按时间排序

分别考虑传送门和任务，令 g[s][i] 表示“传送门状态为 $s$ 完成了 $i$ 个任务，现在身处某一个传送门的最小时间”，令 f[s][i] 表示“传送门状态为 $s$ 刚完成了任务 $i$ 时可以完成的最大任务数”

对于每种传送门状态，预处理出它到每个地点（传送门和任务）的最短路程，分四种情况转移：

  • 传送门到传送门，直接用预处理
  • 传送门到任务，判断可行后用预处理
  • 任务到传送门，要么直接走要么用传送
  • 任务到任务，要么直接走要么用传送，要判断可行

时间为 $O(2^n m^2)$

代码

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
#include <bits/stdc++.h>
#define STC static
#define lowbit(x) (x & -x)
#define dis(a, b) (abs(a.x - b.x) + abs(a.y - b.y))
using namespace std;
const int N = 14 + 5, M = 100 + 5, NN = (1 << 14) + 5;
int n, m, nn, ans = 0;
struct Door
{
    int x, y;
} d[N];
struct Task
{
    int x, y, t;
    bool operator < (const Task& task) const { return t < task.t; }
} ta[M];
int td[NN][N], tt[NN][M]; //td:to_door,tt:to_task
int f[NN][M], g[NN][M], lg2[NN];
int main()
{
    scanf("%d %d", &n, &m), nn = 1 << n;
    for (int i = 1; i <= n; ++i) scanf("%d %d", &d[i].x, &d[i].y);
    for (int i = 1; i <= m; ++i) scanf("%d %d %d", &ta[i].x, &ta[i].y, &ta[i].t);
    sort(ta + 1, ta + 1 + m);
    memset(td, 0x3f, sizeof td), memset(tt, 0x3f, sizeof tt);
    lg2[1] = 0;
    for (int i = 2; i <= nn; ++i) lg2[i] = lg2[i >> 1] + 1;
    for (int s = 1, j = lowbit(s); s < nn; ++s, j = lowbit(s))
    {
        for (int i = 1; i <= n; ++i) td[s][i] = min(td[s ^ j][i], dis(d[lg2[j] + 1], d[i]));
        for (int i = 1; i <= m; ++i) tt[s][i] = min(tt[s ^ j][i], dis(d[lg2[j] + 1], ta[i]));
    }
    memset(f, 0xcf, sizeof f), memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++i) g[1 << (i - 1)][0] = 0;
    for (int i = 1; i <= m; ++i) f[0][i] = 1;
    for (int s = 0; s < nn; ++s)
        for (int i = 0; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j) if (!((s >> (j - 1)) & 1)) g[s ^ (1 << (j - 1))][i] = min(g[s][i] + td[s][j], g[s ^ (1 << (j - 1))][i]); //door to door
            for (int j = 1; j <= m; ++j) if (g[s][i] + tt[s][j] <= ta[j].t) f[s][j] = max(i + 1, f[s][j]); //door to task
            for (int j = 1; j <= n; ++j) if (!((s >> (j - 1)) & 1) && f[s][i] > 0) g[s ^ (1 << (j - 1))][f[s][i]] = min(ta[i].t + min(td[s][j], dis(ta[i], d[j])), g[s ^ (1 << (j - 1))][f[s][i]]); //task to door
            for (int j = i + 1; j <= m; ++j) if (ta[i].t + min(dis(ta[i], ta[j]), tt[s][j]) <= ta[j].t) f[s][j] = max(f[s][j], f[s][i] + 1); //task to task
            ans = max(ans, f[s][i]);
        }
    printf("%d\n", ans);
    return 0;
}