コレクション [yukicoder No.798] - はまやんはまやんはまやん

前提知識

DPテク2「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」

解説

買うか買わないかという問題なので、ナップサック系DP感があるので、そこから考える。
順番が決まっていない所を考えると、ちょうどパラメタ2つなので、うまくソートして系かなと思いつく。
DPテクの「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」を使う。
　
どのようにソートするかであるが、買うものが既に決まっているときを考えると、傾きがより大きいものから買っていけば最適に買える。
そのため、順番はBで昇順ソートすれば良いと分かる。
後は、買うか買わないかなので、
dp[i][get] := i番目まででget個買うときの最小金額
を普通のナップサックDPで作っていけばいい。
奇数の日に0円で購入できるシステムは商品がN個あった場合は、floor(N/3)個分はそのシステムが使えるので、
買うべき個数はN-floor(N/3)となる。
よって、dp[N][N-floor(N/3)]が答え。

int N, A[2010], B[2010];
ll dp[2010][2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i] >> B[i];

    vector<int> ord;
    rep(i, 0, N) ord.push_back(i);
    sort(all(ord), [&](int a, int b) {return B[a] > B[b]; });

    rep(i, 0, N + 1) rep(get, 0, N + 1) dp[i][get] = infl;
    dp[0][0] = 0;
    rep(i, 0, N) rep(get, 0, N) {
        ll a = A[ord[i]];
        ll b = B[ord[i]];

        chmin(dp[i + 1][get], dp[i][get]);
        chmin(dp[i + 1][get + 1], dp[i][get] + a + b * get);
    }

    cout << dp[N][N - N / 3] << endl;
}