25個の整数の反省文。
自力で解けなかったので反省しています。この問題で使ったテクについてメモします。
間違っていたら教えてね!
あとこれは解説じゃないです。
大小関係が定まっているかつDPの問題は小さい方から見てけ!
これはもちろん思いつきました。ただ使えませんでした。
使ったテク2
bitDPは制約から判断しろ
これももちろん出来ました。ただこれも使えませんでした。
xi,j≠0 を満たす整数組 (i,j)(1≦i≦5,1≦j≦5) は 5 個以上存在する。
これで一発でbitDPとわかるだろ、20といえばbitDP
使ったテク3
bitにおいて、forループで計算されたあとたされることはない
これは初めて気づきました。
これはどういうことかというと、
dp[101(2)]+=dp[100(2)]で、101はもうすでに計算されて二度とforループが回ってこない、ということはないということです。
それはそうだけれども、まあいいでしょ、僕は驚いたので。
使ったテク4
座標をbitDPで保存する
うん、これは驚いた。
テク1を使うことによって、何が省略されるか、を考えるべき。
使ったテク5
適さないものを除外
適したものを足すより適さないものを足すほうが簡単にかけることがあります。
ぼくがやるべきこと
綺麗にノートにまとめる
整理しないとだめだってn回言ってる