Shilcare

Knight Moves

Time Limit: 1000MS
 
Memory Limit: 30000K

Total Submissions: 12076
 
Accepted: 5287

Description

Background
Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position...

这道题是经典题目“石子合并”的变形。同样也是用动态规划来解。

用dp[i, j]表示从第 i 堆开始的 j 堆混合物合并所释放的最少烟雾量，sum[i, k]表示从第 i 堆开始的 j 堆

混合物合并后的颜色。显然有状态转移方程：

dp[i, j] = min{dp[i, k] + dp[i + k, j - k] + sum[i, k] * sum[i + k, j - k]} &nbs...

这是Codeforces上的一道题目。