poj3280 cheapest palindrome
区間DPらしい。 蟻本の練習問題。 基本的なDPって書いてあったのに、できなかったけど()
普通に文字列周りの問題が壊滅的にできないと思った。全然できんし。
これがわかってたらという事柄をあげる
- 全探索の方向
- 最小条件のクリア
解答はこの方のを見れば、かなりわかりやすいと思う。
全探索の方向
"abcdef"という文字列があった時、この問題の場合は、c, bc, cd, bcd, abcd, bcde, abcdeっていうのを先頭からやっていく感じだった。わかんなかったな〜
最小条件のクリア
これは、リンク先の解説に書いてあるんだけど、"abcba"というのがあって、cをみたとき、bcを回文にするには、cの左を消すか、bを右に新たに付け足すという動作をすることになって、結局それのどちらがコストが小さいのかというと付け足すコストと消すコストの小さい方になる、このことは、具体的にメモしないとわかんなかったな。もちろんすでに左右対称ならコストは0になる。
区間DPできるようになりテェな
