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$ だけ小さくできます。

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