题目大意

给定一个长度为 $N$ 的整数序列 $a_1, a_2, a_3, \ldots, a_N$。现在，请你将这个序列整理为一个非降序列，并输出最小的总成本。

序列整理的方法非常简单。每次你可以选择序列的某个元素，将它移动到指定位置，而你所需要付出的成本就是这个元素的数值。

例如，对于序列 $7, 1, 2, 3, 1, 10$。我们可以将 $7$ 移动到 $10$ 之前，并将第二个 $1$ 移到序列开头，此时总成本是 $7+1=8$。但如果先将 $1, 2, 3$ 移到序列开头，再将第二个 $1$ 移到序列开头，那么总成本就只需要 $1+2+3+1=7$，少于前一个方案。

$2 \le N \le 500$，$0 \le a_i \le 10^{100}$。

思路

首先，我们先观察，之后发现如果要让一个元素到达自己的位置，只有两个可能。自己挪或者把前面不符合规定的全挪走。也就只有动与不动两种情况。

那我们先想一想动的情况吧。越想越会发现动的情况并不好考虑。这是因为它们的分布不均匀一个元素不是很好去判断能不能动。那我们考虑不动的情况。

之后，如果不动也就能发现所有不动的元素自己成一个非降子序列！ 这就好办了。我们就正常求和最大的非降子序列即可。最后用总和减去这个和就是动的也就是答案。

$dp[i]=dp[j]+a[i](a[j]\leq a[i])$

注意要用高精度

代码

#include <iostream>

using namespace std;
typedef long long ll;
const ll MAXN = 500 + 5;

string add(string na, string nb) {
    long long A[1000] = {0}, B[1000] = {0}, ans[1000] = {0};
    ll l = max(na.length(), nb.length());
    for (ll i = na.length() - 1, j = 1; i >= 0; i--, j++) {
        A[j] = na[i] - '0';
    }
    for (ll i = nb.length() - 1, j = 1; i >= 0; i--, j++) {
        B[j] = nb[i] - '0';
    }
    for (ll i = 1; i <= l; ++i) {
        ans[i] += A[i] + B[i];
        ans[i + 1] = ans[i] / 10;
        ans[i] %= 10;
    }
    if (ans[l + 1] != 0) {
        l++;
    }
    string z = "";
    for (ll i = l; i >= 1; --i) {
        z += ans[i] + '0';
    }
    return z;
}

string sub(string na, string nb) {
    long long A[1000] = {0}, B[1000] = {0}, ans[1000] = {0};
    ll l = max(na.length(), nb.length());
    for (ll i = na.length() - 1, j = 1; i >= 0; i--, j++) {
        A[j] = na[i] - '0';
    }
    for (ll i = nb.length() - 1, j = 1; i >= 0; i--, j++) {
        B[j] = nb[i] - '0';
    }
    for (ll i = 1; i <= l; ++i) {
        if (A[i] < B[i]) {
            A[i + 1] -= 1;
            A[i] += 10;
        }
        ans[i] = A[i] - B[i];
    }
    while ((ans[l] == 0) && l > 1) {
        l--;
    }
    string z = "";
    for (ll i = l; i >= 1; --i) {
        z += ans[i] + '0';
    }
    return z;
}

bool bigger(string na, string nb) {
    if (na == nb) {
        return true;
    }
    if (na.size() < nb.size()) {
        return false;
    }
    if (na.size() > nb.size()) {
        return true;
    }
    return na > nb;
}

bool smaller(string na, string nb) {
    if (na == nb) {
        return true;
    }
    if (na.size() > nb.size()) {
        return false;
    }
    if (na.size() < nb.size()) {
        return true;
    }
    return na < nb;
}

string a[MAXN], dp[MAXN];
ll n;

int main() {
    scanf("%lld", &n);
    string sum = "0";
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum = add(sum, a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        dp[i] = a[i];
        for (int j = 1; j < i; ++j) {
            if (smaller(a[j], a[i])) {
                string K = add(dp[j], a[i]);
                if (bigger(K, dp[i])) {
                    dp[i] = K;
                }
            }
        }
    }
    string Ans = sum;
    for (int i = 1; i <= n; ++i) {
        string K = sub(sum, dp[i]);
        if (smaller(K, Ans)) {
            Ans = K;
        }
    }
    cout << Ans << endl;
    return 0;
}
复制代码

总结

本题告诉我们要多尝试一些路。如果一个路怎么走都走不通时就要换一条路想一想了。本题的关键点就在于从不动的角度切入，一旦切入本题就变得轻而易举了。要先分析究竟是在求什么，如果别的路径最终也能走到这里也要考虑去走。