No.798 コレクション

No.798 コレクション - yukicoder

思考

無料で手に入るというのを無視して

買うもの選ぶという風に問題を読み替えたい

集めた個数は日数から分かるので

dp[i][j] := i日目にj番目を選ぶ組み合わせ

のようにしたくなった

しかし、最適解は左から順番に選ぶとは限らない（困った）

そこで、買う物が決まっている状況を考えた、すると係数が大きいものを先に選んだほうがいいことに気付いた

よって、abのペアをbを降順にソートすれば上のdpが使える

遷移はj未満のkで

dp[i][j] = min(dp[i-1][k] + a[j] + i * b[j]  )

答えは手に入れた個数がn以上になるiでmin(dp[i])

#323530 No.798 コレクション - yukicoder

void solve() {
    cin >> n;
    na2(a, b, n);
    sortp(a, b, sdfi);//a,bをvector<P>として、secondを降順にソートする
    vvi(dp, n + 2, n + 2, linf);
    a.insert(a.begin(), 0);//0日目に無を食べたことにするため
    b.insert(b.begin(), 0);
    dp[0][0] = 0;//1 index で0日目
    vi rumi(n + 1);
    //もらう
    rep(i, 1, n + 1) {
        rumi = dp[i - 1];
        rep(j, 1, n + 1)chmin(rumi[j], rumi[j - 1]);
        rep(j, 1, n + 1) {
            int pre = rumi[j - 1];
            if (pre == linf)con;
            chmin(dp[i][j], pre + a[j] + b[j] * (i - 1));
        }
    }
    int eat = 0;
    rep(i, 1, n + 1) {
        eat++;
        if (i % 2 == 0)eat++;
        if (eat >= n)fin(min(dp[i]));
    }
}