10003 - Cutting SticksTime limit: 3.000 seconds |
题意：
要将一段木头的n(n<50)个位置切开。切开花费为所切木头长度的长度。问切完这n个地方的最小花费。
思路：
可以逆向思维。将木头合成一整段。合并花费为合并后的长度。所以可以很快得到O(n^3)的算法。对于n比较小来说完全够用了。dp[i][j]表示合并完[i,j]的最小花费。dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])。k
10003 - Cutting SticksTime limit: 3.000 seconds |
题意：
要将一段木头的n(n<50)个位置切开。切开花费为所切木头长度的长度。问切完这n个地方的最小花费。
思路：
可以逆向思维。将木头合成一整段。合并花费为合并后的长度。所以可以很快得到O(n^3)的算法。对于n比较小来说完全够用了。dp[i][j]表示合并完[i,j]的最小花费。dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])。k