题解 ATabc334F Christmas Present 2

由 hycqwq 发布

小蒟蒻想不出 $O(n)$ 的解法,来交一发二维 dp 加优化的题解。

Problem

圣诞老人要按顺序给 $n$ 个人送礼物,每个人(包括它自己)家都有一个坐标,而圣诞老人手上最多只能拿 $k$ 个礼物(这就意味着他可能要在送完某些人之后回家补充礼物),求他给所有人送完礼物再回到自己家所需要走的最短距离。

Solution

考虑 $dp_{i, j}$ 表示当前已经送完了前 $i$ 个人的礼物,(送完第 $i$ 个人之后)手上还有 $j$ 个礼物,当前在第 $i$ 个人的家中,需要走的最短路程。

我们用 $dis(a, b)$ 表示第 $a, b$ 个人的家之间的距离,其中第 $0$ 个人是圣诞老人。

同时,一个数组的下标为负数 $-i$,表示这个数组的倒数第 $i$ 个元素。

为了方便,我们认为圣诞老人每次补充礼物都会将礼物数量补充到 $k$ 个。

1. 初值

对于任意 $1 \le i \le n, 1 \le j \le k$ 有 $dp_{i, j} = +\infty$。

另外,$dp_{1, k - 1} = dis(0, 1)$。

2. 递推

在前往第 $i$ 个人家送礼物时,有两种选择:

  1. 直接从第 $i - 1$ 个人家去送,此时对于任意 $1 \le j \le k - 1$ 有:
    $$dp_{i, j - 1} = \min(dp_{i, j - 1}, dp_{i - 1, j} + dis(i - 1, i))$$
  2. 先回家补充礼物再去送,此时对于任意 $0 \le j \le k - 1$ 有:
    $$dp_{i, k - 1} = \min(dp_{i, k - 1}, dp_{i - 1, j} + dis(i - 1, 0) + dis(0, i))$$

注:

  1. 这里的 $j$ 表示上一次送完礼物后(即在送本次礼物之前),手上还有的礼物数量。
  2. 当 $j = 0$ 时,必须先回家补充礼物(这不是废话吗)。

3. 答案

由于我们增加了「我们认为圣诞老人每次补充礼物都会将礼物数量补充到 $k$ 个」这一限制,所以在计算答案时需要枚举所有可能的礼物数量,取路程的最小值,最后加上圣诞老人回家的路程,即

$$ans = (\min_{j = 0}^{k - 1} dp_{n, j}) + dis(n, 0)$$

4. 优化

现在我们的这个算法的复杂度为 $O(nk)$,显然是会超时的(当然还有内存超限,但是用个滚动数组就可以解决),于是我们要考虑一下优化方法。

我们发现,(在 $i$ 相等时)当存在剩余礼物比当前更多,而所需的最小路程比当前更小或相等时,我们没有必要对其最小路程进行计算,因为我们已经可以确定当前方案一定不是最优的方案。

所以我们设定数组 $v_i$ 来从大到小(请记住这一性质,后续优化会用到)存储送完前 $i$ 个人后,可能是最优方案的剩余礼物数 $j$。

换句话说,只有 $dp_{i, v_{i, 1}}, dp_{i, v_{i, 2}}, \cdots, dp_{i, v_{i, -1}}$ 可能是最优的答案,所以对于下一次的递推我们也只对 $v_i$ 中的 $j$ 进行递推。

特别地,$v_1 = \{k - 1\}$。

为了实现这个优化,我们在更新 $dp_i$ 时需按照 $j$ 从大到小的顺序进行更新。

关于数组 $v_i$ 的具体求法,请参考代码。


接下来我们又要回到最开始的问题上:初值。

为什么要在这个时候考虑初值的问题呢?我们在上面提到了:

当然还有内存超限,但是用个滚动数组就可以解决

于是这样就出现了一个新的问题:如果对于每个 $i$,都要对 $dp_i$ 中的所有位置赋初值 $+\infty$,那么时间复杂度不就又变成了 $O(nk)$ 吗?

要解决这个问题,我们需要考虑我们对 $dp$ 数组的更新。

我们再次回到上文。(省略了一些无关紧要的部分,下同)

  1. ……,此时对于任意 $1 \le j \le k - 1$ 有:
    $$dp_{i, \color{red}{j - 1}} = \cdots$$
  2. ……,此时对于任意 $0 \le j \le k - 1$ 有:
    $$dp_{i, \color{red}{k - 1}} = \cdots$$

请注意上面的标红部分。可以发现,对于所有 $1 \le j \le k - 1$,$dp_{i, j - 1}$ 只会被更新一次,只有 $dp_{i, k - 1}$ 会被更新多次。

所以我们只需要对 $dp_{i, k - 1}$ 设置初值 $+\infty$ 即可。


(下面是一个很小的优化,如果不加不会对时间复杂度构成太大的影响,但还是希望各位看一下,代码中也加上了这个优化)

但是,真的到此为止了吗?

我们对于第二种情况的状态转移方程是:

  1. ……,此时对于任意 $0 \le j \le k - 1$ 有:
    $$dp_{i, k - 1} = \min(dp_{i, k - 1}, dp_{i - 1, j} + dis(i - 1, 0) + dis(0, i))$$

我们可以将这里的状态转移方程改写为:

$$dp_{i, k - 1} = \min(dp_{i, k - 1}, (\min_{j = 0}^{k - 1} dp_{i - 1, j}) + dis(i - 1, 0) + dis(0, i))$$

而对于最小的 $dp_{i, j}$,一定有 $j$ 最小,因为比它更小的一定会被排除,不会用于本轮更新。

所以我们可以得到:

$$dp_{i, k - 1} = \min(dp_{i, k - 1}, dp_{i - 1, v_{i - 1, -1}} + dis(i - 1, 0) + dis(0, i))$$

于是,我们把 $dp_{i, k - 1}$ 的更新也减少到了 $1$ 次。


加了这三个优化后,代码跑得飞快,最慢的点只需约 $115\text{ms}$ 即可通过此题。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int infi = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fll;
#define elif else if
#define il inline

int n, k;
ll sx, sy;
ll x[200005], y[200005];
double dp[2/*200005*/][200005]; // dp[i][j] 表示送完前i个人,手上还有j礼物,最少要走多远(当前在i号人的家中)
vector<int> v[2/*200005*/]; // v[i] 表示送完前i个人,只可能剩多少个礼物(如果被完爆,即当存在剩下礼物更多,而走的路可以更少或相同时,就不计入)

double dis(ll x1, ll y1, ll x2, ll y2)
{
    return sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main()
{
    cin >> n >> k >> sx >> sy;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    dp[1][k - 1] = dis(sx, sy, x[1], y[1]);
    v[1].push_back(k - 1);
    for (int i = 2; i <= n; i++)
    {
        double mnd = infl; // 目前剩余礼物比j多的情况中,最少需要走多少路
        dp[i % 2][k - 1] = infl;
        v[i % 2].clear();
        // 当前有j个礼物,在(x[i-1],y[i-1])
        // 如果先回家拿
        int j = v[(i - 1) % 2].back(); // 剩余礼物最少的,走的路一定是最少的,因为如果走的路更多一定会被排除
        dp[i % 2][k - 1] = min(dp[i % 2][k - 1], dp[(i - 1) % 2][j] + dis(x[i - 1], y[i - 1], sx, sy) + dis(sx, sy, x[i], y[i]));
        mnd = min(mnd, dp[i % 2][k - 1]);
        v[i % 2].push_back(k - 1);
        // 如果直接从这里去送
        for (auto j : v[(i - 1) % 2])
            if (j > 0) // 必须还有礼物才行,不然没礼物送了
            {
                dp[i % 2][j - 1] = dp[(i - 1) % 2][j] + dis(x[i - 1], y[i - 1], x[i], y[i]);
                if (mnd > dp[i % 2][j - 1]) // 如果剩余礼物更少,走的路却没有更少,就被“完爆”了,一定不是最优
                    v[i % 2].push_back(j - 1);
                mnd = min(mnd, dp[i % 2][j - 1]);
            }
    }
    double ans = infl;
    for (auto j : v[n % 2])
        ans = min(ans, dp[n % 2][j]);
    cout << fixed << setprecision(15) << ans + dis(x[n], y[n], sx, sy) << endl; // 最后还要回家
    return 0;
}

暂无评论

发表评论