Rustコトハジメ

Rustで競技プログラミングをやる人の覚書のようなものです。

典型DP: L「猫」ふつうのDP。3乗だが実際には通る

これより前の問題の方が遙かに難しいと思う。

https://atcoder.jp/contests/tdpc/tasks/tdpc_cat

問題

猫がn匹をこの順番に並べたい。

猫iと猫jを距離1以下に配置すると、あらかじめ与えられるf[i][j]が得点として得られる。

猫間の距離を工夫して得点を最大化せよ。

制約: n=105, |f|=1000

解法

ある猫iから見て左側距離1以下に猫k匹がいる場合の最大値をdp[i][k]とおいてDPすればよい。

遷移では、そのkのうち右側w=[0,k]の部分とさらに得点加算させる場合を考えればよい。

こうやってあるiから見た時の左側長さで見ていく方が実装がわかりやすいと思う。

実装

AtCoderコンパイラが古いせいで2回CEしました。自然なコードが書けなくて萎えるわ。ループは3重だけど、実際にはそんなにいかないので、500msで間に合う。こういう場合にどうやって計算量を見積もればいいかわからんが、とりあえず「なんとか行けそうだ」と読んで出してみてTLEする(通ったらラッキー)しかないと思う。

fn solve() {
    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    input!{
        n:usize,
        f:[[i64;n];n],
    }
    let mut fsum = vec![vec![];n];
    for i in 0..n {
        let mut dp = vec![0];
        let mut x = vec![];
        for k in (0..i).rev() {
            x.push(f[i][k]);
        }
        for k in 0..i {
            let v = dp[k] + x[k];
            dp.push(v);
        }
        fsum[i] = dp;
    }
    let mut dp = dvec![-1<<30;n+1,n+1];
    dp[0][0] = 0;
    for i in 0..n {
        for k in 0..incl(i) {
            for w in 0..incl(k) {
                chmax!(dp[i+1][w+1], dp[i][k] + fsum[i][w]);
            }
            chmax!(dp[i+1][0], dp[i][k]);
        }
    }
    let mut maxv = std::i64::MIN;
    for k in 0..n+1 {
        chmax!(maxv, dp[n][k]);
    }
    writeln!(out,"{}",2*maxv);
}