题意:现在要买若干种价值的珍珠,但买某种珍珠必须多付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;
}
}
个人原创,转载请注明:三江小渡
我猜你可能也喜欢:
三江小渡
pureisle-记录成长旅程
【POJ1260】Pearls (动态规划)
No Comments - Leave a comment