uva 11400 lrj-P275 动态规划

本文主要是介绍uva 11400 lrj-P275 动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

见刘汝佳入门书籍 P275

dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*a[i].c+a[i].k);

题解：

见刘汝佳入门书籍 P275

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;int dp[1010],sum[1010];
struct Lamp
{int v, k, c, l;bool operator < (const Lamp& rhs) const {return v < rhs.v;}
}a[1010];int main()
{int n;//freopen("in.txt","r",stdin);while(scanf("%d",&n),n){for(int i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].v,&a[i].k,&a[i].c,&a[i].l);sort(a+1,a+1+n);sum[0]=0;for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i].l;dp[0]=0;for(int i=1;i<=n;i++) {dp[i]=sum[i]*a[i].c+a[i].k;for(int j=0;j<i;j++) {dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*a[i].c+a[i].k);}}printf("%d\n",dp[n]);}return 0;
}

这篇关于uva 11400 lrj-P275 动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---