洛谷 P1070 道路游戏 题解

发表于 | 分类于 | | 热度: ℃

Description

环形马路上有 $n$ 个工厂，两个相邻工厂由一段马路连接。以某个工厂为起点，按顺时针将这 $n$ 个工厂编号为 $1-n$，第 $n$ 个工厂和第 $1$ 个工厂连接在一起。将连接工厂的 $n$ 段马路编号为 $1-n$，第 $i$ 段马路连接第 $i$ 个工厂和第 $i+1$ 个工厂 $(1≤i<n)$，第 $n$ 段马路连接第 $n$ 个工厂和第 $1$ 个工厂。

每个单位时间，每段马路上会出现一些金币，不同时间同一段马路上出现的金币数可能不同。机器人能收集马路上的金币。机器人在工厂购买，机器人一旦被购买，会沿着环形马路按顺时针方向每个单位时间内行走一次，从当前所工厂到达下个工厂，将经过的马路上的金币收集给。环形马路上不能同时存在 $≥2$ 个机器人，每个机器人最多能在环形马路上行走 $p$ 次。每次购买需要给机器人设定行走次数，可以为 $1-p$ 之间的任意整数。机器人行走完规定次数之后会自动消失，必须立刻在任意一个工厂中购买一个机器人。

数据范围：$2≤n≤1000 , 1≤m≤1000 , 1≤p≤m$

这是完整的题面，有一些细节

做法1

$f[i]$ 表示第 $i$ 个时刻的最大值；$c[i]$ 表示在第 $i$ 个工厂购买机器人的花费；$sum[i][j]$ 表示第 $i$ 个时刻走到 $j$ 工厂马路上金币的总数。

转移方程（不考虑环的情况）：

$f[i]=max(f[i],f[i-k]+sum[i][j]-sum[i-k][j-k]-c[j-k])$（$i$ 表示当前单位时间，$j$ 枚举工厂，$k$ 枚举步数）

$sum$ 实际是一个二维前缀和，需要在 $dp$ 之前预处理出来。

Code

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1006;
int n, m, p, f[N], r[N][N], sum[N][N], c[N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return f * x;
}

int main()
{
    n = read(), m = read(), p = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            r[i % n][j] = read();
    for(int i = 0; i < n; i++) scanf("%d", &c[i]);
    for(int i = 1; i <= m; i++)
        for(int j = 0; j < n; j++)
            sum[i][j] = sum[i - 1][(j - 1 + n) % n] + r[j][i];
    memset(f, -0x3f, sizeof(f)); //注意负数答案
    f[0] = 0;
    for(int i = 1; i <= m; i++)
        for(int j = 0; j < n; j++)
            for(int k = 0; k <= min(i, p); k++)
            {
                int x = ((j - k) % n + n) % n;
                f[i] = max(f[i], f[i - k] + sum[i][j] - sum[i - k][x] - c[x]);
            }
    printf("%d", f[m]);
    return 0;
}

复杂度分析

$O(n^3)$？

或许窝可以用事 (xia) 实 (bian) 来说明这个做法的复杂度是正确的。

用几个 $for$ 循环来模拟程序中 $dp$ 的复杂度，$n , m , p$ 取最大值。使计数器累加：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int main()
{
    int a = 0;
    for(int i = 1; i <= 1000; i++)
        for(int j = 1; j <= 1000; j++)
            for(int k = 1; k <= i; k++)
              // 这里实际上是循环到 min(i,1000)
                a++;
    printf("%d", &a);
    return 0;
}

运行结果：7339584

单调队列优化

反正 假装 时间复杂度是过不去毒瘤数据的。加一个单调队列优化。

看看这个式子（无环）
f[i]=max(f[i],f[i-k]+sum[i][j]-sum[i-k][j-k]-c[j-k])
用单调队列维护这个东西
f[i]-sum[i][j]-c[j]（带 $k$ 的东西）

在无环的情况下，实际就是在每条对角线上 $dp$。所以给每条对角线建立一个单调队列，编号为 $j-i$。考虑有环的情况：当 $j$ 达到 $n$，它就会回到 $0$ 上去。而 $i$ 一直 $+1$。对角线每改一次就减掉一个 $n$。所以在有环的情况下，编号就改成了((j-i)%n+n)%n。其他不变。

Code

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
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1006;
int n, m, p, f[N], r[N][N], sum[N][N], c[N], q[N][N];
int head[N], tail[N], b[N][N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return f * x;
}

int main()
{
    n = read(), m = read(), p = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            r[i % n][j] = read();
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &c[i]);
        head[i] = 1, tail[i] = 1;
        q[i][tail[i]] = -c[i];
    }
    for(int i = 1; i <= m; i++)
        for(int j = 0; j < n; j++)
            sum[i][j] = sum[i - 1][(j - 1 + n) % n] + r[j][i];
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            int id = ((j - i) % n + n) % n;
            while(head[id] <= tail[id] && b[id][head[id]] + p < i)
                head[id]++;
            if(head[id] <= tail[id])
                f[i] = max(f[i], q[id][head[id]] + sum[i][j]);
        }
        for(int j = 0; j < n; j++)
        {
            int id = ((j - i) % n + n) % n;
            int rec = f[i] - sum[i][j] - c[j];
            while(head[id] <= tail[id] && q[id][tail[id]] <= rec) tail[id]--;
            b[id][++tail[id]] = i;
            q[id][tail[id]] = rec;
        }
    }
    printf("%d", f[m]);
    return 0;
}