Cutting Sticks UVA - 10003（DP 仍有不明白的地方）

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

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

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

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

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

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

递归代码：

 #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[];

 int dp[][];

 int DFS(int i, int j){

     if(i - j <= ) return ;// 如果不需要切割，那么需要的价值就是0

     if(dp[i][j] < inf) return dp[i][j];// 情况不能再分，则返回dp[i][j]的值

     for(int k = i +  ; k < j ; k++)

         dp[i][j] = min(dp[i][j],DFS(i,k) + DFS(k,j) + cut[j] - cut[i]);// 对于每一个子情况用DFS进行搜索，来获取最优情况。

     return dp[i][j];// 这里的dp[i][j] 就是最优解了

 }

 int main(){

     while(~scanf("%d",&l) && l != ){

         memset(dp,inf,sizeof(dp));

         scanf("%d",&n);

         for(int i =  ; i <= n ; i++){

             scanf("%d",&cut[i]);

         }

         cut[] = ;

         cut[n + ] = l;

         int ans = DFS(,n+);

         printf("The minimum cutting is %d.\n",ans);

     }

     return ;

 }

递归代码

数组代码：

#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[];

int dp[][];

int main(){

    while(~scanf("%d",&l) && l != ){

        memset(dp,inf,sizeof(dp));

        scanf("%d",&n);

        for(int i =  ; i <= n ; i++){

            scanf("%d",&cut[i]);

        }

        cut[] = ;

        cut[n + ] = l;

        for(int i =  ; i <= n +  ; i++) dp[i][i] = ;

        for(int i = n +  ; i >=  ; i--){// 这里从n+1到0进行循环，可以先把子结构的最优解算好，在应用到父结构里面。

            for(int j = i ; j <= n +   ; j++){

                for(int k = i ; k <= j ; k++){

                    dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + ][j] + cut[j] - cut[i - ]);//博主还是不太明白为什么这里的要减去cut[i - 1]而不是cut[i].

                }

            }

        }

//        int ans = DFS(0,n+1);

        int ans = dp[][n + ];而且这里输出的是dp[][n + ]而不是dp[][n +]

        printf("The minimum cutting is %d.\n",ans);

    }

    return ;

}

数组代码

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

巴特西

Cutting Sticks UVA - 10003（DP 仍有不明白的地方）

最新文章

热门文章