首页 > 代码库 > UVA 10003 - Cutting Sticks

UVA 10003 - Cutting Sticks

  题目链接Click Here~

  题意分析:

     给一根长为L的木棒,然后给出要切的N处地方。要你用最少的花费完成这项任务。而花费是如何计算的呢?就是用当前木棒的长度是多少,那么花费就是多少。

算法分析:

    运用记忆化的过程可以缩减很多时间,本题的实质是区间DP。原题是经典的石子合并问题。如果,感觉不好理解可以想想图论中的Flody模型。

状态转移方程:dp[i][j] = min(dp[i][j],solve(i,k)+solve(k,j)+len[j]-len[i])本质就是flody的模型转换。

运用到记忆化搜索的时候,终止条件一般有两个,一个是根据题目的要求可以推出,另一个当然是为了避免重复计算而直接运用以前得出的结果。

本题的条件一是if(i+1 == j) return 0;即:合并的区间只有自己一个。