首页 > 代码库 > zoj 1563 - Pearls

zoj 1563 - Pearls

题目:有不同品质的珍珠,品量高的珍珠价钱高。买珍珠的价钱计算方式:(购买数量+10)×单价;

            质量低的珍珠可以用质量高的珍珠替代,给出要买的珍珠类型和数量,求买完所有珍珠所要的最低价钱。

分析:dp,贪心。每种珠宝 都是整体处理时才会有最小价格,即要么和比他贵的一起买,要么自己单独买。

            按照价格递增的顺序dp,只有价格高的可以代替价格低的;

            这里有一个结论,代替购买不会交叉只会是连续的;

            即p[i] < p[j] < p[k],则不会出现i用k代替,而j不用k代替而直接买j;

           (这时用j代替i花的钱更少:p[j]*(a[i]+a[j])+p[k]*a[k] < p[j]*a[j]+p[k](a[i]+a[k]))

            所以每各阶段,枚举sum(a[j],..,a[i]){ 其中1 ≤ j ≤ i }(即枚所有i代替前面的可能性)更新即可。

说明:躺了一会。。睡不着。。终于A了。。还想早点睡的说。。(2011-09-26 02:46)

#include <stdio.h>
#include <stdlib.h>

#define INF 100000001

int a[ 101 ];
int p[ 101 ];
int F[ 101 ];

int main()
{
    int T,N;
    while ( scanf("%d",&T) != EOF )
    for ( int t = 1 ; t <= T ; ++ 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 )
            F[ i ] = INF;
        F[ 0 ] = 0;
        
        for ( int i = 1 ; i <= N ; ++ i ) {
            int sum = 10;
            for ( int j = i ; j >= 1 ; -- j ) {
                sum += a[ j ];
                if ( F[ i ] > F[ j-1 ] + sum*p[ i ] )
                    F[ i ] = F[ j-1 ] + sum*p[ i ];
            }
        }
        
        printf("%d\n",F[ N ]);
    }
    return 0;
}


zoj 1563 - Pearls