ABC288-E Wish List
(Test/AtCoder/abc288_e.test.cpp)

• View this file on GitHub
• Last update: 2024-02-09 20:29:43+09:00
• Problem: https://atcoder.jp/contests/abc288/tasks/abc288_e

番号昇順に買うか買わないかを決定する。 $C_j$ の寄与は後ろの要素には全く影響されないので、そこからDPを考えることができる。

$\text{DP}_{i, j}$ $i$ 番目までの商品を考慮した、 $j$ 個の商品を既に購入している時の最小値

区間minの形になっているのでSparseTableで高速化できる。

Depends on

• max演算モノイド (Src/Algebra/Monoid/MaxMonoid.hpp)
• Sparse Table (Src/DataStructure/SparseTable/SparseTable.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "https://atcoder.jp/contests/abc288/tasks/abc288_e"

#include "../../Src/DataStructure/SparseTable/SparseTable.hpp"
#include "../../Src/Algebra/Monoid/MaxMonoid.hpp"

#include <iostream>
#include <vector>

using namespace zawa;
using M = MaxMonoid<int>;
using MD = M::Element;

int main() {
    int n, m; std::cin >> n >> m;
    std::vector<int> a(n);
    for (auto& v : a) std::cin >> v;
    std::vector<MD> c(n);
    for (auto& v : c) {
        int x; std::cin >> x;
        v = -x;
    }
    std::vector<int> x(n);
    for (int _{} ; _ < m ; _++) {
        int v; std::cin >> v;
        x[v - 1] = true;
    }

    SparseTable<M> spt(c);
    
    const long long INF{(long long)1e18};
    std::vector<long long> dp(n + 1, INF);
    dp[0] = 0;

    for (int i{} ; i < n ; i++) {
        std::vector<long long> nxt(n + 1, INF);
        for (int j{} ; j <= i ; j++) {
            if (!x[i]) {
                nxt[j] = std::min(nxt[j], dp[j]);
            }
            long long cost{(long long)a[i] - spt.product(i - j, i + 1).value()};
            nxt[j + 1] = std::min(nxt[j + 1], dp[j] + cost);
        }
        dp = std::move(nxt);
    }

    long long ans{*std::min_element(dp.begin(), dp.end())};
    std::cout << ans << '\n';
}

#line 1 "Test/AtCoder/abc288_e.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc288/tasks/abc288_e"

#line 2 "Src/DataStructure/SparseTable/SparseTable.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/DataStructure/SparseTable/SparseTable.hpp"

#include <vector>
#include <cassert>
#include <ostream>

namespace zawa {

template <class Structure>
class SparseTable {
private:
    using Value = typename Structure::Element;
    std::vector<u32> L;
    std::vector<std::vector<Value>> dat;
public:

    SparseTable() : L{}, dat{} {}
    SparseTable(const std::vector<Value>& a) : L(a.size() + 1), dat{} {
        for (u32 i{1} ; i < L.size() ; i++) {
            L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
        }
        dat.resize(L.back() + 1);
        dat[0] = a;
        for (u32 i{1}, len{2} ; i < dat.size() ; i++, len <<= 1) {
            dat[i] = dat[i - 1];
            for (u32 j{} ; j + len - 1 < dat[i].size() ; j++) {
                dat[i][j] = Structure::operation(dat[i - 1][j], dat[i - 1][j + (len >> 1)]);
            }
        }
    }

    Value product(u32 l, u32 r) const {
        assert(l <= r);
        assert(l < dat[0].size());
        assert(r <= dat[0].size());
        u32 now{L[r - l]};
        return Structure::operation(dat[now][l], dat[now][r - (1 << now)]);
    }

    friend std::ostream& operator<<(std::ostream& os, const SparseTable<Structure>& spt) {
        for (u32 i{}, len{1} ; i < spt.dat.size() ; i++, len <<= 1) {
            os << "length = " << len << '\n';
            for (u32 j{} ; j + len - 1 < spt.dat[i].size() ; j++) {
                os << spt.dat[i][j] << (j + len == spt.dat[i].size() ? '\n' : ' ');
            }
        }
        return os;
    }
};

} // namespace zawa
#line 2 "Src/Algebra/Monoid/MaxMonoid.hpp"

#include <algorithm>
#include <limits>
#include <optional>

namespace zawa {

template <class T>
class MaxMonoid {
public:
    using Element = std::optional<T>;
    static constexpr Element identity() noexcept {
        return std::nullopt;
    }
    static constexpr Element operation(const Element& l, const Element& r) noexcept {
        if (l and r) {
            return std::max(l, r);
        }
        else if (l) {
            return l;
        }
        else if (r) {
            return r;
        }
        else {
            return std::nullopt;
        }
    }
};

} // namespace zawa
#line 5 "Test/AtCoder/abc288_e.test.cpp"

#include <iostream>
#line 8 "Test/AtCoder/abc288_e.test.cpp"

using namespace zawa;
using M = MaxMonoid<int>;
using MD = M::Element;

int main() {
    int n, m; std::cin >> n >> m;
    std::vector<int> a(n);
    for (auto& v : a) std::cin >> v;
    std::vector<MD> c(n);
    for (auto& v : c) {
        int x; std::cin >> x;
        v = -x;
    }
    std::vector<int> x(n);
    for (int _{} ; _ < m ; _++) {
        int v; std::cin >> v;
        x[v - 1] = true;
    }

    SparseTable<M> spt(c);
    
    const long long INF{(long long)1e18};
    std::vector<long long> dp(n + 1, INF);
    dp[0] = 0;

    for (int i{} ; i < n ; i++) {
        std::vector<long long> nxt(n + 1, INF);
        for (int j{} ; j <= i ; j++) {
            if (!x[i]) {
                nxt[j] = std::min(nxt[j], dp[j]);
            }
            long long cost{(long long)a[i] - spt.product(i - j, i + 1).value()};
            nxt[j + 1] = std::min(nxt[j + 1], dp[j] + cost);
        }
        dp = std::move(nxt);
    }

    long long ans{*std::min_element(dp.begin(), dp.end())};
    std::cout << ans << '\n';
}

Back to top page