E1. Voting (Easy Version) Educational Codeforces Round 75

Problem - E1 - Codeforces

解法
mを昇順にpを降順にソートして、後ろから考える。
ここでiを買う必要が無いのは、自分の前にいるi人とi以降で買ったj人でi+j >= m[i]となる場合である
この時、i-1までを埋めることが出来ればiまで埋まる事が分かる
i+j< m[i]ならiを買わないといけない。
よってdp[i][j] := iより後ろでj人買っている場合にi以降で必要なコストとして上のように遷移する

https://codeforces.com/contest/1251/submission/64069398

signed main() {
    din(Q);
    while (Q--) {
        in(N);
        vi A, V;
        na2(A, V, N);
        sortp(A, V, fisd);
        //i人目以降でj人かっている場合
        vvi(dp, N + 1, N + 1, linf);
        dp[N][0] = 0;
        rer(i, N - 1) {
            rep(j, N + 1) {
                int a = A[i], v = V[i];
                //前と後ろで埋まる
                if (i + j >= a) {
                    chmi(dp[i][j], dp[i + 1][j]);
                }
                //買う
                if (j + 1 <= N) {
                    chmi(dp[i][j + 1], dp[i + 1][j] + v);
                }
            }
        }
        cout << min(dp[0 ]) << endl;
    }
}