DP--钢条切割

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 #define MAX_LENGTH 11
 6 
 7 void CutRod(int * P, int p_last, int * R, int r_last);
 8 
 9 
10 int main()
11 {
12     int P[MAX_LENGTH] = { 0,1,5,8,9,10,17,17,20,24,30 };
13     int k_th = 20;
14 
15     int* R = (int*)malloc((k_th+1)*sizeof(int));
16     memset(R, 0, k_th * sizeof(int));
17     CutRod(P,MAX_LENGTH - 1, R,k_th);
18     for (int i = 1; i <= k_th; i++)
19     {
20         printf("%d ",R[i]);
21     }
22     printf("
");
23     // 1 5 8 10 13 17 18 22 25 30 31 35 38 40 43 47 48 52 55 60
24     system("pause");
25     return 0;
26 }
27 
28 
29 
30 void CutRod(int * P, int p_last, int * R, int r_last)
31 {
32     for (int i = 1; i <= r_last; i++)
33     {
34         int max_profit = P[i];
35         if (i > p_last)
36             max_profit = -1;
37         for (int j = 1; j <= i; j++)
38         {
39             max_profit = max_profit > R[j] + R[i - j] ? max_profit : R[j] + R[i - j];
40         }
41         R[i] = max_profit;
42     }
43 }