AtCoder Beginner Contest 261 (D) DP (F) Fenwick Tree

1. D DP

https://atcoder.jp/contests/abc261/tasks/abc261_d

1.1 Problem Statement

1.2 分析

1.3 code

my code

#include <bits/stdc++.h>

using namespace std;

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

    int n, m;
    cin >> n >> m;

    vector<long long> x(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i];
    } 

    map<int, long long> mp;
    for (int i = 0; i < m; i++)
    {
        int c, y;
        cin >> c >> y;

        mp[c] = y;
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
    dp[1][1] = x[1] + mp[1];

    for (int i = 2; i <= n; i++)
    {
        long long cur = 0;
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] + x[i] + mp[j];
            cur = max(cur, dp[i - 1][j - 1]);
        }

        dp[i][0] = cur;
    }

    long long ans = 0;
    for (int i = 0; i <= n; i++)
    {
        ans = max(ans, dp[n][i]);
    }

    cout << ans << endl;

    return 0;
}

Jiangly’s code

#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1E18;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;
    
    std::vector<int> v(n);
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }
    
    std::vector<int> w(n + 1);
    for (int i = 0; i < m; i++) {
        int c, y;
        std::cin >> c >> y;
        w[c] = y;
    }
    
    std::vector<i64> dp(n + 1, -inf);
    dp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        std::vector<i64> g(n + 1, -inf);
        for (int x = 0; x <= i; x++) {
            g[x + 1] = std::max(g[x + 1], dp[x] + v[i] + w[x + 1]);
            g[0] = std::max(g[0], dp[x]);
        }
        dp = g;
    }
    
    std::cout << *std::max_element(dp.begin(), dp.end()) << "\n";
    
    return 0;
}

2. F Fenwick Tree

https://atcoder.jp/contests/abc261/tasks/abc261_f

2.1 Problem Statement

$n$ 个球从左到右排列, 颜色分别是 $C_i$, 球上的数字分别是 $X_i$

重新排列小球, 使得上面的数字形成 non-decreasing

为了实现目的, 可以进行以下操作:

• 选择一个下标, $1 \le i \le n - 1$
• 如果第 $i$ 与 $i+1$ 的小球颜色不同, 代价为 1(颜色相同则代价为0)
• 交换两个小球

问: 实现目的的最小代价???

2.2 分析

最小代价为下标对 $(i, j)$ 的数量, 满足:

\[1 \le i < j \le n, C_i \ne C_j, X_i > X_j\]

2.3 code

#include <bits/stdc++.h>

using i64 = long long;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n) : n(n), a(n) {}

    void add(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] += v;
        }
    } 

    T sum(int x) {
        T ans = 0;
        for (int i = x; i > 0; i -= i & -i) {
            ans += a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<int> c(n), x(n);
    std::vector<std::vector<int>> f(n);
    for (int i = 0; i < n; i++) {
        std::cin >> c[i];
        c[i]--;
        f[c[i]].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
        x[i]--;
    }
    
    Fenwick<int> fen(n);
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        ans += fen.rangeSum(x[i] + 1, n);
        fen.add(x[i], 1);
    }
    
    for (int i = 0; i < n; i++) {
        fen.add(x[i], -1);
    }
    
    for (int c = 0; c < n; c++) {
        for (auto i : f[c]) {
            ans -= fen.rangeSum(x[i] + 1, n);
            fen.add(x[i], 1);
        }
        for (auto i : f[c]) {
            fen.add(x[i], -1);
        }
    }
    
    std::cout << ans << "\n";
    
    return 0;
}