首页 > 代码库 > 区间DP与贪心算法的联系(uav Cutting Sticks && poj Fence Repair)

区间DP与贪心算法的联系(uav Cutting Sticks && poj Fence Repair)

  因为,这两题有着似乎一样的解法所以将其放在一起总结比较,以达到更好的区分二者的区别所在。


一、区间DP


uva的Cutting Sticks是一道典型的模板题。

题目描述: 

  有一根长度为l的木棍,木棍上面有m个切割点,每一次切割都要付出当前木棍长度的代价,问怎样切割有最小代价。

区间DP的定义:

   区间动态规划问题一般都是考虑,对于每段区间,他们的最优值都是由几段更小区间的最优值得到,是分治思想的一种应用,将一个区间问题不断划分为更小的区间直至一个元素组成的区间,枚举他们的组合,求合并后的最优值。

解法:
   设F[i,j](1<=i<=j<=n)表示区间[i,j]内的数字相加的最小代价 , 最小区间F[i,i]=0(一个数字无法合并,∴代价为0)每次用变量k(i<=k<=j-1)将区间分为[i,k]和[k+1,j]两段

区间DP模板,代码:

for(intp = 1 ; p <= n ; p++){      //p是区间的长度,作为阶段
  for(int i = 1 ; i <= n ; i++){   //i是穷举区间的起点
      int j = i+p-1;               //j为区间的终点
      for(int k = i ; k < j ; k++)//状态转移
         dp[i][j] = min{dp[i][k]+dp[k+1][j]+w[i][j]};//这个是看题目意思,有的是要从k开始不是k+1
         dp[i][j]= max{dp[i][k]+dp[k+1][j]+w[i][j]};
      }
}


改题解法:
   对于这一题,如果我们只对最左边的切割点到最右边的切割点进行DP,那么得到的答案肯定是错的,因为不是整个区间,所以我们必须在木棍的做左边和左右边分别增加一个点,那么得到的就是整个区间,再对这个区间进行DP求解即可。


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 50 + 10;
const int INF = ~0U >> 2;
int w[MAXN],dp[MAXN][MAXN];
int L,n;

int solve(){
    n++;
    for(int i = 0;i <= n;++i)
        for(int j = i+1;j <= n;++j)
            dp[i][j] = (i+1 == j ? 0 : INF);

    w[0] = 0; w[n] = L;
    for(int p = 1;p <= n;++p){            //区间长度
        for(int s = 0;s <= n-p;++s){       // 起始位置
            int e = s + p;                //终点
            for(int k = s+1;k < e;++k){    //状态转移
                dp[s][e] = min(dp[s][e],dp[s][k] + dp[k][e] + w[e] - w[s]);
            }
        }
    }
    return dp[0][n];
}
int main()
{
    while(scanf("%d",&L),L){
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i){
            scanf("%d",&w[i]);
        }
        printf("The minimum cutting is %d.\n",solve());
    }
    return 0;
}





区间DP与贪心算法的联系(uav Cutting Sticks && poj Fence Repair)