137D. Palindromes

Codeforces C++ C+++

概要

文字列をk個以下の回文に分割するのに必要な最小の文字の書き換えを求める
分からなかったのでEditorialを読んだ
まずi文字目からj文字目を回文にするコストcnt[i][j]を計算する
初めからi文字をj個に分けた時のコストz[i][j]は
z[i][j] = min { z[k][j-1] + c[k][i-1] } でうまくkで回せばok
500^3なのでC++で解いた

ソース

非常に汚い
https://github.com/mkut/cf/tree/master/01-99/98/137D/c++.cpp(C+++)
https://github.com/mkut/cf/tree/master/01-99/98/137D/main.cpp

出展

Round #98 Div.2 D