这个问题有很多变形（经典的dp）
线性的 环形的。。
至于某些online judge的小规模已经解决，pku 1738 数据规模特别大
dp基本不可能，现在还做出来，ms要用Optimal Alphabetic Binary Search Tree
这个正在研究中
规模比较小时dp思想不难 类似矩阵乘积的dp思想
dp[i][k] 表示从i开始的k个（包括i）
dp[i][k]=min{dp[i][r]+dp[i+r][k-r]+sum[i][i+k-1]}
//sum[i][i+k-1]表示从i,i+1,..,i+k-1的和 这里其实一维就可以表示了
阅读(971) | 评论(0) | 转发(0) |
