P5052 [COCI2017-2018#7] Go 题解

---

首先我们需要知道，我们经过一个房间就一定会把里面的小精灵拿来换糖吃，所以我们只需要关注自己到或者没到某一个小精灵的房间，这样就可以直接离散化，把题目中的 $n$ 减少了一个数量级。

我们考虑怎么转移。
因为我们经过的区间一定是空的，同时我们经过的区间一定是连续的，那么我们可以考虑尝试扩展我们当前已经走过的区间。

那我们记 $f(l,r,t,[0/1])$，为当前我们已经走过了区间 $[l,r]$，使用的时间为 $t$，现在在区间的左端点 / 右端点处。
然后考虑我们是如何扩展到当前区间的：

$$\begin{array}{}\text{(1)}& f(l,r,t,0)& =max(f(l+1,r,max(t-dis(a_l,a_{l+1}),0),0),f(l+1,r,max(t-dis(a_l,a_r),0),1))+b_l[t<c_l]\text{(2)}& f(l,r,t,1)& =max(f(l,r-1,max(t-dis(a_r,a_{r-1}),0),1),f(l,r-1,max(t-dis(a_l,a_r),0),0))+b_r[t<c_r]\end{array}$$

题目顺便帮我们指定了开始的位置 $k$，这样我们可以用一个空的精灵 $\{k,0,0\}$ 来作为开始位置，当然如果 $k$ 的位置上已经有了精灵那就直接用就好了。

然后是对区间赋初值。
我们首先对每一个小精灵算出从起点直奔其所在位置的答案：

for(int i = st + 1; i <= m; i++)
    f[st][i][dis(st, i)][1] = f[st][i - 1][dis(st, i - 1)][1] + (dis(st, i) < a[i].t ? a[i].b : 0);
for(int i = st - 1; i; i--)
    f[i][st][dis(i, st)][0] = f[i + 1][st][dis(i + 1, st)][0] + (dis(st, i) < a[i].t ? a[i].b : 0);

然后是转移：

我们在外层枚举时间 $t$，然后再内层从 $[k,k]$ 开始枚举区间。
时间最大枚举到 $\underset{i=1}{\overset{m}{max}}(t_i)$，再往后枚举的话答案绝对不会增加。

for(int t = 1; t <= maxt; t++)
{
    for(int l = st - 1; l >= 1; l--)
    {
        for(int r = st + 1; r <= m; r++)
        {
            f[l][r][t][0] = max(f[l + 1][r][max(t - dis(l, l + 1), 0)][0], f[l + 1][r][max(t - dis(l, r), 0)][1]) + (t < a[l].t ? a[l].b : 0);
            f[l][r][t][1] = max(f[l][r - 1][max(t - dis(r, r - 1), 0)][1], f[l][r - 1][max(t - dis(l, r), 0)][0]) + (t < a[r].t ? a[r].b : 0);
        }
    }
}

答案的话就在每一次转移的时候统计一下就好了。

代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 110, M = 2010;
int n, m, k;
struct Node
{
    int a, b, t;
    bool operator < (const Node &rhs)const { return a < rhs.a; }
};
Node a[N];
int dis(int i, int j) { return abs(a[i].a - a[j].a); }
int f[N][N][M][2];
int main()
{
    int maxt = 0;
    scanf("%d%d%d", &n, &k, &m);
    bool flag = false;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].t);
        if(a[i].a == k)flag = true;
        maxt = max(maxt, a[i].t);
    }
    if(!flag)a[++m] = { k,0,0 };
    sort(a + 1, a + 1 + m);
    int st = -1;
    for(int i = 1; i <= m; i++)
        if(a[i].a == k)st = i;
    int ans = 0;
    memset(f, -63, sizeof(f));
    f[st][st][0][0] = f[st][st][0][1] = a[st].b;
    for(int i = st + 1; i <= m; i++)
    {
        f[st][i][dis(st, i)][1] = f[st][i - 1][dis(st, i - 1)][1] + (dis(st, i) < a[i].t ? a[i].b : 0);
        ans = max(ans, f[st][i][dis(st, i)][1]);
    }
    for(int i = st - 1; i; i--)
    {
        f[i][st][dis(i, st)][0] = f[i + 1][st][dis(i + 1, st)][0] + (dis(st, i) < a[i].t ? a[i].b : 0);
        ans = max(ans, f[i][st][dis(st, i)][0]);
    }
    for(int t = 1; t <= maxt; t++)
    {
        for(int l = st - 1; l >= 1; l--)
        {
            for(int r = st + 1; r <= m; r++)
            {
                f[l][r][t][0] = max(f[l + 1][r][max(t - dis(l, l + 1), 0)][0], f[l + 1][r][max(t - dis(l, r), 0)][1]) + (t < a[l].t ? a[l].b : 0);
                f[l][r][t][1] = max(f[l][r - 1][max(t - dis(r, r - 1), 0)][1], f[l][r - 1][max(t - dis(l, r), 0)][0]) + (t < a[r].t ? a[r].b : 0);
                ans = max(ans, max(f[l][r][t][0], f[l][r][t][1]));
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}