G. 小红的数轴移动（二）

Description

小红站在数轴的x点上，她准备进行n次操作，每次操作如下： 若小红站在原点，则原地不动。否则向原点的方向，移动 距离。 小红可以自己选择操作的先后次序。她希望给出一个方案，使得最终移动的总距离最小，你能帮帮她吗？

Solution

排列问题并不好做，我们先做如下观察：

observation1：该问题等价于对序列分配权值 求移动总距离最小。

Brief Proof

证明二者等价性，我们尝试用转化后的问题构造出原问题的一个解。

将操作分为正向和反向两种移动方式，。 如果此时位置，我们使用操作直到，反之亦然。

因为两种操作位移和一定是。若想到达原点至少将两个集合操作用完，同时又只有在原点才会出现无法用尽的情况，所以一定能构造一个解。

由observation1就变成了一个简单的组合优化问题，可以很轻松的用DP解决。

tip1： 写的过程中很容易把问题歪到小红一定会走到原点的情况，如果获得200分考虑是否漏考虑了小红用完所有操作也走不到原点的情况。

Code

#include <bits/stdc++.h>
using namespace std;

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

    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (auto& it : a) cin >> it;
    int sa = accumulate(a.begin(), a.end(), 0);
    vector<vector<int>> f(n + 1, vector<int>(sa * 2 + 1, INT_MAX / 2));
    f[0][x + sa] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = -sa; j <= sa; j++) {
            f[i + 1][j + sa] = min(f[i + 1][j + sa], f[i][j + sa]);
            if (j - a[i] + sa >= 0)
                f[i + 1][j + sa] = min(f[i + 1][j + sa], a[i] + f[i][j - a[i] + sa]);
            if (j + a[i] + sa <= 2 * sa)
                f[i + 1][j + sa] = min(f[i + 1][j + sa], a[i] + f[i][j + a[i] + sa]);
        }
    }
    if (f[n][sa] > 1e9) {
        cout << sa << "\n";
        for (int i = 0; i < n; i++) cout << i + 1 << " ";
        return 0;
    }
    cout << f[n][sa] << "\n";
    vector<int> pos, positive, negtive;
    pos.emplace_back(0);
    for (int i = n - 1; i >= 0; i--) {
        int now = pos.back();
        if (now - a[i] + sa >= 0 && f[i + 1][now + sa] == a[i] + f[i][now - a[i] + sa]) {
            pos.emplace_back(now - a[i]);
            positive.emplace_back(i);
        } else if (now + a[i] + sa <= 2 * sa && f[i + 1][now + sa] == a[i] + f[i][now + a[i] + sa]) {
            pos.emplace_back(now + a[i]);
            negtive.emplace_back(i);
        }
    }
    // assert(pos.back() == x);
    vector<int> opseq, usd(n);
    int now = x;
    while (now != 0) {
        // cout<<"from "<<now<<" to ";
        if (now > 0) {
            int t = negtive.back();
            negtive.pop_back();
            usd[t] = 1;
            opseq.emplace_back(t);
            now -= a[t];
        } else if (now < 0) {
            int t = positive.back();
            positive.pop_back();
            usd[t] = 1;
            opseq.emplace_back(t);
            now += a[t];
        }
        // cout << now << "\n";
    }
    // reverse(opseq.begin(), opseq.end());
    for (int i = 0; i < n; i++)
        if (!usd[i]) opseq.emplace_back(i);
    for (auto it : opseq) cout << it + 1 << " ";   
    return 0;
}

Appendix

00