补题链接：Here

经典手速场

1509A. Average Height

题意：要找出最大不平衡对序列

先输出奇数，然后输出偶数

void solve() {
    int n;
    cin >> n;
    vector<int> odd, even;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        if (x & 1) odd.push_back(x);
        else
            even.push_back(x);
    }
    for (int x : odd) cout << x << " ";
    for (int x : even) cout << x << " ";
    cout << "\n";
}

1509B. TMT Document

题意：给定一个 T-M字符串，求问是否能全拆分为 TMT 子序列

思路：

要能组成 TMT 就要是 T、M顺序一定并 cntT = 2 * cntM 和 \(n \% 3== 0\)

void solve() {
    int n;
    string s;
    cin >> n >> s;
    int ct = 0, cm = 0;
    bool f = true;
    for (int i = 0; f && i < n; ++i) {
        s[i] == 'T' ? ct++ : cm++;
        if (cm > ct || (ct > 2 * cm + n / 3 - cm)) f = false;
    }
    cout << (f && cm * 2 == ct && n % 3 == 0 ? "YES\n" : "NO\n");
}

1509C. The Sports Festival

题意：

学生会要参加接力赛，每位成员跑步速度为 \(a_i\) ，给定定义：

\[d_i = max(a_1,a_2,\dots,a_i) - min(a_1,a_2,\dots,a_i) \]

求出最小的 \(\sum_{i = 1}^n d_i\)

思路：

待补。

using ll = long long;
ll dp[2005][2005];
int n;
int A[2005];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> A[i];
    sort(A + 1, A + n + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) dp[i][j] = 1e18;
    for (int i = 1; i <= n; ++i) dp[i][i] = 0;
    for (int len = 1; len < n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            if (j < n) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + A[j + 1] - A[i]);
            if (i > 1) dp[i - 1][j] = min(dp[i - 1][j], dp[i][j] + A[j] - A[i - 1]);
        }
    }
    cout << dp[1][n] << '\n';
}

另外一种写法

using ll = long long;
void solve() {
    int n;
    cin >> n;
    vector<ll> s(n);
    for (ll &x : s) cin >> x;
    sort(s.begin(), s.end());
    vector<ll> dp0(n), dp1(n);
    for (int k = 1; k < n; ++k) {
        for (int i = k; i < n; ++i)
            dp1[i] = min(dp0[i - 1], dp0[i]) + s[i] - s[i - k];
        swap(dp0, dp1);
    }
    cout << dp0[n - 1] << '\n';
}