题解 AT_abc334_f Christmas Present 2

· · 题解

小蒟蒻想不出 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;
}