hdu 1300 Pearls （dp）

hdu 1300 Pearls （dp）

題目大意：

多種珍珠，每次選購都要在原有的數量上加上10.

例如：買5個單價是10的珍珠。需要的花費是（5+10）*10= 150.買100個單價是20的珍珠
需要的花費是（100+10）*20= 2200.總共需要的花費是150+2200=2350.如果把珍珠的質量提高了。需要的105個
珍珠都買單價是20的。也就是說都買質量好的。總的花費是（5+100+10）*20= 2300.在兩組數據看來。珍珠都
買了高品質的了，而且花費也少了！
問題是怎麼樣能花費最少買珍珠！

思路分析：

dp [i] 表示 買到第 i 中珍珠的最優解

狀態轉移： dp [i] = min (dp[j] + v) v 表示 j-i 之間的珍珠都以i的價格購入的價格。

#include 
#include 
#include 
#include 
#define maxn 105
using namespace std;

struct node
{
    int price,num;
}a[105];
int dp[maxn];
int sum[maxn];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].num,&a[i].price);
            sum[i]=sum[i-1]+a[i].num;
        }

        memset(dp,0x3f,sizeof dp);

        dp[0]=0;

        for(int i=1;i<=n;i++)
        {
            for(int j=0;j