Number skip card

解説

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

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

実装