JOI難易度６ ナイルドットコム

問題原文

https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf

問題要旨

日間、毎日 個の商品の中から１つを選んで購入する。
各商品の値段は毎日変動する。また、同じ商品を２日連続で買うと１割引で買え、３日以上連続で買うと３割引で買える。
払う金額を最小化せよ。

• 
• 

解法

「定価で買った場合」「１割引で買った場合」「３割引で買った場合」のテーブルを持ってdpをする。
遷移は、

• 定価で買うテーブル → 全テーブルの最小値 + 当該商品の値段
• １割引で買うテーブル → 定価で買うテーブルの同じ列 + 当該商品の値段 × 0.9
• ３割引で買うテーブル → min(１割引で買うテーブルの同じ列, ３割引で買うテーブルの同じ列） + 当該商品の値段 × 0.7

になる。

実装

時間制限もメモリ制限も厳しいのでnumpyを使ってみた。
うまくかけてるのかもわからない。

import sys
import numpy as np
my_input = sys.stdin.readline

N, D = map(int, my_input().split())

BEST = 0
INF = 10 ** 9
dp1 = np.zeros(N)  # 普通に購入する
dp2 = np.full(N, INF)  # 2日続けて購入する
dp3 = np.full(N, INF)  # 3日以上続けて購入する

for i in range(D):
    items = np.array(list(map(int, my_input().split())))
    if i >= 2:
        dp3 = np.minimum(dp2, dp3) + items * 0.7

    if i >= 1:
        dp2 = dp1 + items * 0.9

    dp1 = items + BEST
    BEST = min(dp1.min(), dp2.min(), dp3.min())

print(int(BEST))

感想

いぇいいぇいいぇい。
ちょっと不思議な遷移だなと思いました。慣れていきたい。