本文主要是介绍poj-1260-Pearls-dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题目我真是无力吐槽了。，，
题意：
从质量差到质量好的顺序给你需要买的珍珠的数量和单价。
让你求如何花最少的钱买到所有的珍珠（质量差的可以用质量好的来替换）；
买一种单价为p的珍珠n个花费（n+10）*p；即每种珍珠需要多花10*p的钱。
做法:
用dp【i】表示买到第i种珍珠花的钱。
则：dp【i】=min（dp【i】，dp[j]+(sum[i]-sum[j]+10)*p[i])）；
注意：
珍珠的质量越高，但是单价不一定越高。一定要注意。
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int n,i;scanf("%d",&n);int a[1001];int p[1001];int sum[1001];sum[0]=0;for(i=1;i<=n;i++){scanf("%d%d",&a[i],&p[i]);sum[i]=a[i]+sum[i-1];}int nums;a[0]=0;p[0]=0;int dp[1001];dp[0]=0;for(i=1;i<=n;i++){int j;dp[i]=dp[i-1]+a[i]*p[i]+10*p[i];for(j=0;j<i;j++)dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*p[i]);}printf("%d\n",dp[n]);}return 0;
}
这篇关于poj-1260-Pearls-dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
