Number skip card

2 secs 1024 MB

解説

dp[i][j] = Aをi番目まで、Bをj番目までペアを決めた時のペナルティの最小値とします。

遷移は以下の通りです。

Aにスキップカードを入れる場合

$B_j$ のペアはスキップカードになりペアが決まります。 $A_i$ はまだペアが決まってないのでそのままです。よって、dpの遷移は以下のようになります。

dp[i][j+1] = dp[i][j] + K

Bにスキップカードを入れる場合も同様に考えることができます。

スキップカードをAもBも入れない場合

$A_i$ と $B_j$ がペアとなります。よって、dpの遷移は以下のようになります。

dp[i+1][j+1] = dp[i][j] + A_i - B_j

スキップカード同士がペアになることはありません。なぜならその部分を抜くことでペナルティの総和が $K$ だけ小さくできます。

各遷移先で最小になるように値を更新していけばよいです。

実装

xxxxxxxxxx
 
use proconio::*;
​
const INF: i64 = 1e18 as i64 + 100;
​
macro_rules! chmin {
    ( $a: expr, $b: expr) => {
        {
            if $a > $b {
                $a = $b;
                true
            } else {
                false
            }
        }
    }
}
​
fn main() {
    input! {
        n: usize,
        k: i64,
        a: [i64; n],
        b: [i64; n]
    }
​
    let mut dp = vec![vec![INF; n]; n];
    dp[0][0] = a[0] - b[0];
    for i in 0..n-1 {
        for j in 0..n-1 {
            chmin!(dp[i][j+1], dp[i][j] + k);
            chmin!(dp[i+1][j], dp[i][j] + k);
            chmin!(dp[i+1][j+1], dp[i][j] + a[i+1] - b[j+1]);
        }
    }
    
    println!("{}", dp[n-1][n-1]);
}
​