首页 > 代码库 > uva10003 Cutting Sticks

uva10003 Cutting Sticks

2024-07-26 05:35:34   210人阅读

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944

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

在左右两端加上两个端点，区间dp即可。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 10000 5 using namespace std; 6 const int inf=1<<29; 7  8 int l,n; 9 int c[maxn];10 int dp[1001][1001];11 12 13 int main()14 {15     while(scanf("%d",&l)!=EOF)16     {17         if(l==0) break;18         scanf("%d",&n);19         for(int i=1; i<=n; i++)20         {21             scanf("%d",&c[i]);22         }23         c[0]=0; c[n+1]=l;24         memset(dp,0,sizeof(dp));25         for(int i=2; i<=n+1; i++)26         {27             for(int j=0; j+i<=n+1; j++)28             {29                 int min1=inf;30                 for(int k=j+1; k<j+i; k++)31                 {32                     if(min1>dp[j][k]+dp[k][j+i])33                     {34                         min1=dp[j][k]+dp[k][j+i];35                     }36                 }37                 dp[j][j+i]=min1+c[j+i]-c[j];38             }39         }40         printf("The minimum cutting is %d.\n",dp[0][n+1]);41     }42     return 0;43 }
View Code

 

uva10003 Cutting Sticks


联系
我们