【POJ1260】Pearls (动态规划)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 03 日

题意:现在要买若干种价值的珍珠,但买某种珍珠必须多付10颗此种珍珠的价钱,一颗珍珠可以用比它贵的珍珠充数,因此有时候用贵的珍珠来代替便宜的可能更省钱,输入要买的若干种珍珠,在可用高价珍珠充数的条件下,问最少需要花费多少钱.
假设有价值从x……y的珍珠,则在购买最大价值为z(x #include<iostream> #include<algorithm> using namespace std; int sum[101],price[101],res[101]; int main() { freopen("1.txt","r",stdin); int n,num,i,j,sumprice; cin>>n; while(n--){ cin>>num; sumprice=0; for (i=1;i<=num;i++){ cin>>sum[i]>>price[i]; sum[i] +=sum[i-1]; } for (i=1;i<=num;i++) { res[i]=(sum[i]+10)*price[i]; for(j=1;j<i;j++) res[i]=min(res[i],(sum[i]-sum[j]+10)*price[i]+res[j]); } cout<<res[num]<<endl; } } 个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日