Cutting Sticks UVA

题意：对一根长为l的木棒进行切割，给出n个切割点，每次切割的价值，等于需要切割的木头长度。

一开始理解错了，认为切割点时根据当前木条的左端点往右推算。

实际上，左端点始终是不变的一直是0，右端点一直是l，切割点就是在0 ~ l 之间的点，而切割时的价值就是切割这个点的时候当前木条的长度。

状态转移方程：dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + cut[j] - cut[i]);

思路就是朝着子区间最优的情况靠拢，然后再求全局最优，由于子结构是包含在父结构中，所以用递归写的代码比较简单易懂。

博主也参考了网上的代码，也有用数组的写法，但是数组写法博主也有还没弄懂的地方。

递归代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<map>
 7 #include<cmath>
 8 #include<queue>
 9 #include<stack>
10 using namespace std;
11 const int inf = 0x3f3f3f3f;
12 int l,n;
13 int cut[100];
14 int dp[100][100];
15 
16 int DFS(int i, int j){
17     if(i - j <= 1) return 0;// 如果不需要切割，那么需要的价值就是0
18     if(dp[i][j] < inf) return dp[i][j];// 情况不能再分，则返回dp[i][j]的值
19     for(int k = i + 1 ; k < j ; k++)
20         dp[i][j] = min(dp[i][j],DFS(i,k) + DFS(k,j) + cut[j] - cut[i]);// 对于每一个子情况用DFS进行搜索，来获取最优情况。
21     return dp[i][j];// 这里的dp[i][j] 就是最优解了
22 }
23 int main(){
24     while(~scanf("%d",&l) && l != 0){
25         memset(dp,inf,sizeof(dp));
26         scanf("%d",&n);
27         for(int i = 1 ; i <= n ; i++){
28             scanf("%d",&cut[i]);
29         }
30         cut[0] = 0;
31         cut[n + 1] = l;
32         int ans = DFS(0,n+1);
33         printf("The minimum cutting is %d.
",ans);
34     }
35     return 0;
36 }

递归代码

数组代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<iostream>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
const int inf = 0x3f3f3f3f;
int l,n;
int cut[100];
int dp[100][100];


int main(){
    while(~scanf("%d",&l) && l != 0){
        memset(dp,inf,sizeof(dp));
        scanf("%d",&n);
        for(int i = 1 ; i <= n ; i++){
            scanf("%d",&cut[i]);
        }
        cut[0] = 0;
        cut[n + 1] = l;
        for(int i = 0 ; i <= n + 1 ; i++) dp[i][i] = 0;
        for(int i = n + 1 ; i >= 0 ; i--){// 这里从n+1到0进行循环，可以先把子结构的最优解算好，在应用到父结构里面。
            for(int j = i ; j <= n + 1  ; j++){
                for(int k = i ; k <= j ; k++){
                    dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j] + cut[j] - cut[i - 1]);//博主还是不太明白为什么这里的要减去cut[i - 1]而不是cut[i].
                }
            }
        }
//        int ans = DFS(0,n+1);
        int ans = dp[1][n + 1];而且这里输出的是dp[1][n + 1]而不是dp[0][n +1]
        printf("The minimum cutting is %d.
",ans);
    }
    return 0;
}

数组代码

一个从很久以前就开始做的梦。