Morris' Blog

2011-06-18 08:06:04Morris

d686. Q10003: Cutting Sticks

內容：

你的任務是替一家叫Analog Cutting Machinery (ACM)的公司切割木棍。切割木棍的成本是根據木棍的長度而定。而且切割木棍的時候每次只切一段。

很顯然的，不同切割的順序會有不同的成本。例如：有一根長10公尺的木棍必須在第2、4、7公尺的地方切割。這個時候就有幾種選擇了。你可以選擇先切2公尺的地方，然後切4公尺的地方，最後切7公尺的地方。這樣的選擇其成本為：10+8+6=24。因為第一次切時木棍長10公尺，第二次切時木棍長8公尺，第三次切時木棍長6公尺。但是如果你選擇先切4公尺的地方，然後切2公尺的地方，最後切7公尺的地方，其成本為：10+4+6=20，這成本就是一個較好的選擇。

你的老闆相信你的電腦能力一定可以找出切割一木棍所需最小的成本。

輸入說明：

每組測試資料3列，第一列有1個整數L（L<1000），代表需要切割的木棍的長度。第二列有一個整數N（N<50），代表需要切的次數。第三列有N個正整數C_i（0 < C_i < L）代表木棍需被切割的地方。這N個整數均不相同，且由小到大排列好。

L=0代表輸入結束。請參考Sample Input。

輸出說明：

對每一組測試資料，輸出最小的切割成本。請參考Sample Output。

範例輸入：

100325 50 751044 5 7 80

範例輸出：

The minimum cutting is 200.The minimum cutting is 22.

提示：

※測資有誤請告知

出處：

UVa 10003 (管理：david942j)

作法 : DP
更新的方法與矩陣乘積鏈相同
你會發現他給的數據，可以利用括弧表示所有可能，而這些可能又要求最小值
採用的也是+，那麼可以知道，一個大括弧［］，可以拆成兩個()()，也就是
［()+()］一定是min+min = min，因此我們從小範圍的［］去處理
而兩個()()，距離不同，則用窮舉，如此一來是O(N^3)
［0,1］［1,2］［2,3］［3,4］...
［0,2］［1,3］［2,4］［3,5］...
［0,3］［1,4］［2,5］［3,6］...

/**********************************************************************************/
/* Problem: d686 "Q10003: Cutting Sticks" from UVa 10003                         */
/* Language: C                                                                   */
/* Result: AC (50ms, 270KB) on ZeroJudge                                         */
/* Author: morris1028 at 2011-06-17 17:03:33                                     */
/**********************************************************************************/

#include<stdio.h>
main() {
   int n, L, A[52] = {0};
   while(scanf("%d", &L) == 1 && L) {
       scanf("%d", &n);
       int DP[52][52] = {}, a, b, c, d;
       for(a = 1; a <= n; a++)
           scanf("%d", &A[a]);
       A[++n] = L;
       for(a = 2; a <= n; a++) {
           for(b= 0, c= a+b; c <= n; b++, c++) {
               int min = 2147483647, t;
               for(d = b+1; d < c; d++) {
                   t = DP[b][d] + DP[d][c] + A[c] - A[b];
                   if(min > t)   min = t;
               }
               DP[b][c] = min;
           }
       }
       printf("The minimum cutting is %d.\n", DP[0][n]);
   }
   return 0;
}

上一篇：d873. Q465: Overflow

下一篇：c100. Unidirectional TSP