ABC288 E問題 Wish List

欲しい商品だけを購入する場合

商品を購入するとき、定価＋追加金額 $C_j$ が必要になります。
定価はどのように商品を購入しても変わりませんが、追加金額 $C_j$ は商品の購入順序によって変わります。
そこで、まず追加金額が最小になる買い方を考えます。

商品番号 $p$ の商品を買う場合、それより前の番号の商品を購入していなければ追加金額は $C_p$ です。
$p$ より小さな番号の商品を1つ購入した後に購入すれば、追加金額は $C_{p-1}$ に変わります。
$p$ より小さな番号の商品を2つ購入した後に購入すれば、追加金額は $C_{p-2}$ に変わります。
商品番号 $p$ の商品が欲しい商品リストの $k$ 番目であれば、追加金額は $C_p, C_{p-1}, C_{p-2},\cdots,C_{p-k+1}$ のいずれかになります。
合計金額が最小になるのは、各商品を追加金額が $C_p, C_{p-1}, C_{p-2},\cdots,C_{p-k+1}$ の最小になったときに購入したときです。
商品番号が大きいほうから見ていって追加金額が最小値になっている商品があれば購入する、を繰り返せば実現できます。

入力例2 では、次のようになります。

商品番号が $20\to 8 \to 1\to 3\to 4\to14\to5\to16$ の順に購入すれば最小金額になります。

欲しい商品以外も購入する場合

入力例2 では、欲しい商品以外に、あと2つ購入すれば商品番号20 の商品を追加金額 2 で購入することができます。
もし、追加購入にかかる金額（定価＋追加金額）より、追加金額の減少額の方が大きければ、追加購入した方がお得です。

どの商品を購入すれば金額が安くなるかを、すべての組み合わせで調べるのは時間がかかりすぎるため、
商品番号が小さいほうから $i$ 番目まで購入するか、購入しないか決めたときの最小金額を dp として動的計画法で計算することを考えます。
商品番号 $i+1$ の商品を購入するとき、追加金額の最小値がいくらになるかは、それまでに何個の商品を購入したかによります。
そのため dp は、「それまでに何個の商品を購入したか」で分けておく必要があり、 dp [ i ] [ j ] (商品番号が小さいほうから $i$ 番目まで、購入した商品数が $j$ 個
のときの最小金額) の計算を行えばよいです。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  # 入力データ
  N,M = readInts()
  A = readInts()
  C = readInts()
  X = readInts()

　must_buy = zeros(Int,N)
  for i = 1:M
    must_buy[X[i]] = 1
  end

  NOTUSED = typemax(Int64)

　dp = fill(NOTUSED,N+1,N+1)

  d(i) = i+1  # 配列のインデックスを 0 始まりするために使う

  dp[d(0),d(0)] = 0

  for i = 1:N
    # 商品番号 i の商品を購入する場合

    Cmin = C[i]  # 追加金額の最小値

    for j = 0 : i-1
      if dp[d(i-1),d(j)] != NOTUSED
        dp[d(i),d(j+1)] = dp[d(i-1),d(j)] + A[i] + Cmin
      end
      if i-j-1 > 0
        Cmin = min(Cmin, C[i-j-1])
      end
    end

    if must_buy[i] != 1
      # 商品番号 i の商品を購入しない場合
      for j = 0 : i-1
        dp[d(i),d(j)] = min(dp[d(i-1),d(j)], dp[d(i),d(j)])
      end
    end

  end

  # 一番安い金額を出力
  ans = typemax(Int64)
  for j = M:N
    ans = min( ans, dp[d(N),d(j)])
  end
  println(ans)

end  # function solve

# main
solve()