問題 動的計画法を使う。 dpn配列に文字列の長さ、dp配列に文字列を格納する。配列の長さはマッチ棒の個数。 dpnを0から順番に調べ、初期値(-1)ではなく、追加したマッチ棒の個数の地点の長さが ①追加したい個所と同じ ・追加したい個所に、追加したい個所と…

問題 解けなかった。 解答PDFを参考にすると、 となるので、配列をDPで更新していけば解けることが分かる。 import sys readline = sys.stdin.readline L = int(input()) dp = [0] * 5 for a in map(int, (readline() for _ in range(L))): back = a % 2 if …

dp_d 動的計画法 通常のナップサック問題。 重さが 105 なので、O(NW)では 107。 pythonでは間に合わなかったため、c++で提出した。 一応、pythonコード c++コード