Project Euler 750

发表于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

Project Euler 750

题目

Optimal Card Stacking

Card Stacking is a game on a computer starting with an array of \(N\) cards labelled \(1,2,\ldots,N\). A stack of cards can be moved by dragging horizontally with the mouse to another stack but only when the resulting stack is in sequence. The goal of the game is to combine the cards into a single stack using minimal total drag distance.

For the given arrangement of \(6\) cards the minimum total distance is \(1 + 3 + 1 + 1 + 2 = 8\).

For \(N\) cards, the cards are arranged so that the card at position \(n\) is \(3^n\bmod(N+1), 1\le n\le N\).

We define \(G(N)\) to be the minimal total drag distance to arrange these cards into a single sequence.

For example, when \(N = 6\) we get the sequence \(3,2,6,4,5,1\) and \(G(6) = 8\).

You are given \(G(16) = 47\).

Find \(G(976)\).

Note: \(G(N)\) is not defined for all values of \(N\).

解决方案

设 \(P(x)\) 表示编号为 \(x\) 的牌在初始排列中的位置（位置编号从 \(1\) 到 \(N\)）。由于每一步合并后都必须保持连续顺序，因此任意中间栈一定对应某个连续牌号区间，也就是 \(i,i+1,\ldots,j\)。这说明问题天然是一个区间动态规划问题。

接下来证明结论：把区间 \(i,\dots,j\) 的牌合并成一个合法顺序栈后，这个栈最终一定停在牌 \(j\) 的原始位置 \(P(j)\)。

当区间长度为 \(1\) 时，结论显然成立。假设所有更短区间都成立。考虑区间 \(i..j\) 的最后一次合并，它一定是由某个切分点 \(k\) 形成的两段合并而成：左段是 \(i,\dots,k,\)右段是 \(k+1,\dots,j.\)为了保证合并后仍是连续顺序，最后一步必须把左段拖到右段上，因此合并后的位置等于右段的位置。

根据归纳假设，右段 \(k+1,\dots,j\) 的位置固定为 \(P(j)\)，所以区间 \(i,\dots,j\) 的位置也固定为 \(P(j)\)。性质得证。

形成区间 \(i,\dots,j\) 的最后一步若在 \(k\) 处分割，则总代价由三部分组成，分别是形成左段 \(i,\dots,k\) 的最小代价；形成右段 \(k+1,\dots,j\) 的最小代价；将左段拖到右段上的拖动距离。由于区间位置固定，第三部分的拖动距离恒为 \(|P(k)-P(j)|\)，不会受到区间外其他牌操作的影响。因此可以进行标准区间 DP。

定义 \(f(i,j)\) 表示把编号从 \(i\) 到 \(j\) 的牌（即 \(i,i+1,\ldots,j\)）合并成一个合法顺序栈的最小总代价。那么状态转移方程为：

\[ f(i,j)= \left\{ \begin{aligned} &0 && \text{if}\quad i=j,\\ &\min_{i\le k<j}\left(f(i,k)+f(k+1,j)+|P(k)-P(j)|\right) && \text{if}\quad i<j. \end{aligned} \right. \]

其中第一行表示单张牌不需要移动，因此代价为\(0\)。第二行则是枚举最后一次合并的切分点 \(k\)，其中 \(i \le k < j\)。则总代价为：左段代价 \(f(i,k),\)右段代价 \(f(k+1,j),\)以及最后一次拖动代价 \(|P(k)-P(j)|.\)

最终答案为：\(G(N)=f(1,N).\)

需要注意的是，题目给出的排列是 \(3^n \bmod (N+1)\)。但这组值未必恰好构成 \(1,\dots,N\) 的一个排列。只有当这 \(N\) 个值恰好是 \(1,\dots,N\) 的一个排列时，题目中的初始布局才合法，\(G(N)\) 才有定义。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 976;
int solve(int n)
{
    vector<int> pos(n);
    int mod = n + 1;
    long long v = 3 % mod;
    for (int p = 0; p < n; ++p)
    {
        pos[(int)v - 1] = p;
        v = v * 3 % mod;
    }

    const int INF = 1e9;
    vector<int> dp(n * n, 0);

    for (int len = 1; len < n; ++len)
    {
        for (int l = 0; l + len < n; ++l)
        {
            int r = l + len;
            int best = INF;
            int pr = pos[r];
            int baseL = l * n;
            int baseR = r * n;
            for (int k = l; k < r; ++k)
            {
                int d = pos[k] - pr;
                if (d < 0)
                    d = -d;
                int cur = dp[baseL + k] + dp[baseR + (k + 1)] + d;
                if (cur < best)
                    best = cur;
            }
            dp[baseL + r] = best;
            dp[baseR + l] = best;
        }
    }
    return dp[n - 1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << solve(N) << '\n';
    return 0;
}