SRM335 Div2 1000

問題

いくつかの数字の配列が与えられる。これをk個のグループに分けたい。ただし、条件として「各グループの数字の分散の値の和が最小となるようなグループ分け」にしなければならない。
この時、分散の和が最小となるグループ分けの「分散の和」を返す。

考え方

再帰でどこまで1つのグループにするかを回すとTLE。
ここで必要なのは「分散の和の最小値」だけなので、DPでいける。

分散の定義から差が大きい数字同士は分散が大きくなってしまうのでソートしておく。
最初にiからjまでの数字の分散をあらかじめ求めてvar[i][j]などにいれておく。
dp[i][j] = 0からjまでの数字をi個のグループに分けたときの最小分散値とすると、
dp[i][j] = Min(dp[i-1][m]+var[m+1][j])で求まる。
これは、0からmまでの数字をi-1個に分けてある場合に、m+1からjまでを一つのグループとすれば、その分散値はdp[i-1][m]+var[m+1][j]となり、mをどこで区切るかループを回してその最小値を探せばいい。