【POJ 1260】Pearls
题意
有n个（n≤100）等级的珍珠，等级越高单价越高，要购买一种等级的珍珠就要多付10*单价，现在需要购买一些等级的珍珠一定数量，若买更高等级的珍珠更便宜则可以买更高等级的珍珠，求最少花费。
分析
我原来想贪心（如果该等级买，不如后一等级多买那么多更优，那就不买该等级），然而是错的，怎么证明不能贪心呢？
网上是这么说的：如果每次贪心的将价格合并到高一级的，那么这样最终的结果并不一定正确，不具有最优子结构的特性。因为可能现在牺牲一点价格，后面的继续合并这样总的价格会更低。所以，其实这题就抽象到了多重背包的问题了。
反正就是要DP嘛。状态转移方程
dp[i]=min(dp[j]+(sum[i]-sum[j]+10)*p[i],dp[i]);（j=0到i-1）
dp[i]表示前i个等级最少花多少钱，sum[i]表示前i个等级共需要多少数量，j是我们截断的位置，表示j+1到i都用i等级的单价购买。
代码
#include<algorithm>
#include<cstdio>
#define N 105
using namespace std;
int t,n,ans,a,p[N],dp[N],sum[N];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d%d",&a,&p[i]);
sum[i]=sum[i-1]+a;
dp[i]=99999999;//也可以dp[i]=dp[i-1]+(a[i]+10)*p[i];
}
for(int i=1; i<=n; i++)
for(int j=0; j<i; j++)
dp[i]=min(dp[j]+(sum[i]-sum[j]+10)*p[i],dp[i]);
printf("%d\n",dp[n]);
}
return 0;
}还有一种写法
#include<algorithm>
#include<cstdio>
#define N 105
using namespace std;
int t,n,ans,a[N],p[N],dp[N],sum;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d%d",&a[i],&p[i]);
for(int i=1; i<=n; i++)
{
dp[i]=99999999;//也可以dp[i]=dp[i-1]+(a[i]+10)*p[i];
sum=0;
for(int j=i-1; j>=0; j--)
{
sum+=a[j+1];
dp[i]=min(dp[j]+(sum+10)*p[i],dp[i]);
}
}
printf("%d\n",dp[n]);
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2016-02-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
