首页 > 代码库 > POJ 1260 Pearls

POJ 1260 Pearls

题意:给你n种珍珠,档次从低到高。每一种珍珠会给你计划要买的数量及单价。要你求出买原固定数量的珍珠,使得档次与价格最优。(每个档次的珍珠花的钱=(计划数量+10)*单价)

我们来看一个例子:

3
1 10
1 11
100 12
首先原计划买的珍珠数量为100+1+1=102   花的钱{(1+10)*10+(1+10)*11+(100+10)*12}=1551

我们按题意优化后:(102+10)*12=1344<1551,所以输出1344

我们可以从题目中看到:

1、题目档次高地珍珠一定比档次低得珍珠单价高

2、我们只能用档次高地替换档次低得珍珠

所以我们可以思考,在到达第i类珍珠的时候,前面的最优为dp[i-1],那么当前未优化的钱是:dp[i-1]+(c[i]+10)*p[i];

优化时,我们枚举i之前的情况,设前j种珍珠的最优是dp[j],所以买第i种珍珠的数量为sum[i]-sum[j].所以优化后的钱是:

dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j]+10)*p[i])

所以AC代码:

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[105],c[105],p[105],sum[105];
int main()
{
    int t,n,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        sum[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d %d",&c[i],&p[i]);
            sum[i]=sum[i-1]+c[i];
        }
        dp[0]=0;
        for(i=1;i<=n;i++)
        {
            dp[i]=(c[i]+10)*p[i]+dp[i-1];
            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;
}