题解 | 道路游戏-NOIP2009普及组复赛B题

题目描述

小新正在玩一个简单的电脑游戏。
游戏中有一条环形马路，马路上有n个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这n 个机器人工厂编号为1~n，因为马路是环形的，所以第n个机器人工厂和第1 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这n段马路也编号为1~n，并规定第i段马路连接第i个机器人工厂和第i+1个机器人工厂（1≤i≤n-1），第n 段马路连接第n个机器人工厂和第1个机器人工厂。
游戏过程中，每个单位时间内，每段马路上都会出现一些金币，金币的数量会随着时间发生变化，即不同单位时间内同一段马路上出现的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在i（1≤i≤ n）号机器人工厂购买了一个机器人，这个机器人会从i 号机器人工厂开始，顺时针在马路上行走，第一次行走会经过i 号马路，到达i+1号机器人工厂（如果i=n，机器人会到达第1个机器人工厂），并将i号马路上的所有金币收集给小新。游戏中，环形马路上不能同时存在2个或者2个以上的机器人，并且每个机器人最多能够在环形马路上行走p次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为1~p之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。
以下是游戏的一些补充说明：
1. 游戏从小新第一次购买机器人开始计时。
2. 购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
3. 购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
4. 在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
5. 购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。
现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费，请你告诉小新，经过m 个单位时间后，扣除购买机器人的花费，小新最多能收集到多少金币。

输入描述:

第一行3个正整数， $n，m，p(2≤n≤1000，1≤m≤1000，1≤p≤m)$ ，意义如题目所述。
接下来的 n 行，每行有m 个正整数，每两个整数之间用一个空格隔开，其中第i行描述了i号马路上每个单位时间内出现的金币数量（1≤金币数量≤100），即第i行的第 $j（1≤j≤m）$ 个数表示第j个单位时间内i号马路上出现的金币数量。
最后一行，有 n 个整数，每两个整数之间用一个空格隔开，其中第i个数表示在i号机器人工厂购买机器人需要花费的金币数量（1≤金币数量≤100）。

输出描述:

共一行，包含1 个整数，表示在m 个单位时间内，扣除购买机器人花费的金币之后，小新最多能收集到多少金币。

示例1

输入

2 3 2
1 2 3
2 3 4
1 2

输出

5

备注

对于40%的数据， $2≤n≤40,1≤m≤40$ 。
对于90%的数据， $2≤n≤200,1≤m≤200$ 。
对于100%的数据， $2≤n≤1000,1≤m≤1000,1≤p≤m$ 。

解答

我们设 $dp[i][j][k]$ 为第 $i$ 单位时间，当前机器人在 $j$ 工厂且走了 $k$ 部的情况，又设 $a[i][j]$ 为第 $i$ 单位时间在 $j$ 工厂的价格。

容易得到：

$dp[i][j][1]=\max_{1⩽j′⩽n,1⩽k′⩽p}\left\{ dp[i−1][j′][k′] \right\}−d[j]+a[i][j]$

而当 $k>1$ 时，

$dp[i][j][k]=dp[i−1][j−1][k−1]+a[i][j]$

用一下滚动数组优化空间，你就发现你ac了！

#include <iostream>
#include <cstdio>
#include <cstring>

#define MAX_N (1000 + 5)
#define MAX_M (1000 + 5)
#define MAX_P (1000 + 5)

using namespace std;

int n, m, p;
int a[MAX_M][MAX_N];
int d[MAX_N];
int dp[2][MAX_N][MAX_P]; 
int ans = -0x7f7f7f7f; 

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for(register int j = 1; j <= n; ++j)
    {
        for(register int i = 1; i <= m; ++i)
        {
            scanf("%d", a[i] + j);
        }
    }
    for(register int i = 1; i <= n; ++i)
    {
        scanf("%d", d + i);
    }
    int tmp = 0;
    for(register int i = 1, bi = 1; i <= m; ++i, bi ^= 1)
    {
        for(register int j = 1; j <= n; ++j)
        {
            dp[bi][j][1] = tmp + a[i][j] - d[j];
        }
        for(register int j = 1; j <= n; ++j)
        {
            for(register int k = 2; k <= i && k <= p; ++k)
            {
                dp[bi][j][k] = dp[bi ^ 1][j == 1 ? n : j - 1][k - 1] + a[i][j];
            }
        }
        tmp = -0x7f7f7f7f;
        for(register int j = 1; j <= n; ++j)
        {
            for(register int k = 1; k <= i && k <= p; ++k)
            {
                tmp = max(tmp, dp[bi][j][k]);
            }
        }
    }
    for(register int j = 1; j <= n; ++j)
    {
        for(register int k = 1; k <= m && k <= p; ++k)
        {
            ans = max(ans, dp[m & 1][j][k]);
        }
    }
    printf("%d", ans);
    return 0;
}

但这显然是数据出水了，我们要优化！

我们把 $dp[i][j][k]$ 改成 $dp[i][j]$ ，表示第 $i$ 单位时间，当前机器人在 $j$ 工厂情况。

又设 $s[i][x]$ 表示第 $1$ 个单位时间从 $x$ 工厂出发一直走到当前的第 $i$ 个单位时间（不用管 $p$ ），收集到的金币和。

根据前面的方程可以得到:

$dp[i][j]=$ $max \begin{cases} \max_{1\leq j'\leq n}& \left\{ dp[i−1][j′]\right\}−d[j]+a[i][j] \\ \max_{i-p+1\leq i'< i}& \left\{ dp[i′][j′]+s[i][x]−s[i′][x] \right\} \end{cases}$

又可以变形：

$dp[i][j]=$ $max \begin{cases} \max_{1\leq j'\leq n}& \left\{ dp[i−1][j′]\right\}−d[j]+s[i][x]−s[i−1][x] \\ \max_{i-p+1\leq i'< i}& \left\{ dp[i′][j′]+s[i][x]−s[i′][x] \right\} \end{cases}$

我们在求完所有的 $dp[i−1][j′]$ 时，其实可以提前预处理一个 $\max_{1\leq j'\leq n}\left\{ dp[i−1][j′] \right\}$

这样又变形为：

$dp[i][j]=$ $max \begin{cases} last−d[j]+s[i][x]−s[i−1][x] \\ \max_{i-p+1\leq i'< i} \left\{ dp[i′][j′]+s[i][x]−s[i′][x] \right\} \end{cases}$

显然第二行的公式可以用单调队列优化，第一行也可以先插入到单调队列，最后再求 $dp[i][j]$ 即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>

#define MAX_N (1000 + 5)
#define MAX_M (1000 + 5)
#define MAX_P (1000 + 5)

using namespace std;

struct Node
{
    int idx, val;
};

int n, m, p;
int a[MAX_M][MAX_N];
int s[MAX_M][MAX_N];
int d[MAX_N];
int dp[MAX_N];
deque <Node> q[MAX_N];

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for(register int j = 1; j <= n; ++j)
    {
        for(register int i = 1; i <= m; ++i)
        {
            scanf("%d", a[i] + j);
        }
    }
    for(register int i = 1; i <= n; ++i)
    {
        scanf("%d", d + i);
    }
    int x = 1;
    for(register int i = 1; i <= m; ++i)
    {
        for(register int j = 1; j <= n; ++j)
        {
            if(j > 1) x = (x == n ? 1 : x + 1);
            s[i][x] = s[i - 1][x] + a[i][j];
        }
    }
    int last = 0;
    Node tmp;
    x = 1;
    for(register int i = 1; i <= m; ++i)
    {
        tmp.idx = i; 
        for(register int j = 1; j <= n; ++j)
        {
            if(j > 1) x = (x == n ? 1 : x + 1);
            if(!q[x].empty() && q[x].front().idx + p == i) q[x].pop_front();
            tmp.val = last - d[j] + a[i][j];
            while(!q[x].empty() && tmp.val >= q[x].back().val + s[i][x] - s[q[x].back().idx][x]) q[x].pop_back();
            q[x].push_back(tmp);
            dp[j] = max(last - d[j] + a[i][j], q[x].front().val + s[i][x] - s[q[x].front().idx][x]);
        }
        last = -0x7f7f7f7f;
        for(register int j = 1; j <= n; ++j)
        {
            last = max(last, dp[j]);
        }
    }
    printf("%d", last);
    return 0;
}

来源：kcn999