uva 10003 lrj-P278 区间dp入门

本文主要是介绍uva 10003 lrj-P278 区间dp入门，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一根棍子的长度，以及n个需要切割的点，每一次切割的代价是这一段需要被切割的长度

问代价最小时的代价值

题解：

区间dp

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[j]-a[i]);

 i 为区间左端点，j 为右端点，k为中间的子问题

dp表示某一个区间的最小切割值

区间dp 的思路，先枚举区间大小，然后枚举区间的起始位置，此时就能知道区间的终止位置

然后枚举中间点，从子问题得到区间 i  到 j 的解

最后就能得到答案

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int a[100],dp[100][100];int main()
{int l,n;//freopen("in.txt","r",stdin);while(scanf("%d",&l),l){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);a[0]=0,a[n+1]=l;memset(dp,0x3f3f3f3f,sizeof(dp));for(int i=1;i<=n;i++)dp[i-1][i]=0;dp[n][n+1]=0;for(int len=2;len<=n+1;len++)for(int i=0,j=i+len;i+len<=n+1;i++,j=i+len)for(int k=i+1;k<j;k++)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[j]-a[i]);printf("The minimum cutting is %d.\n",dp[0][n+1]);}return 0;
}

这篇关于uva 10003 lrj-P278 区间dp入门的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---