三江小渡

题意:现在要买若干种价值的珍珠,但买某种珍珠必须多付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; } } 个人原创，转载请注明：三江小渡

我猜你可能也喜欢：

• 【POJ1692】Crossed Matchings(动态规划DP)
• 【POJ1717】Dominoes （动态规划，背包变形）
• 【POJ2342】Anniversary party（树形动态规划 tree dp）
• 【POJ2823】Sliding Window（单调队列的原理和简单应用）
• 【POJ2411】Mondriaan’s Dream（动态规划）
• 【POJ2479】Maximum sum（动态规划,DP）