题目链接：

题目大意：珠宝店有100种不同质量的珍珠，质量越高价钱越高，为了促进销售，每买一种类型的珍珠，要在原来的基础上必须再买10个。这时一个CFO发现，这种条件下，有时买质量更好的反而更便宜。比如要买10元的珍珠5个，20元的珍珠100个，普通的买法需要(5+10)*10 + (100+10)*20 = 2350，但是如果只买105个价值20元的珍珠，只需要 (5+100+10)*20 = 2300。现在给定要买的珍珠的数量和对应价格，求最少花费

Sample Input

2

2

100 1

100 2

3

1 10

1 11

100 12

 

Sample Output

330

1344

 

分析：令dp[i]表示买前 i 种珍珠的最小花费，则dp[i] = min{dp[j],(珍珠 j 到珍珠 i 的数量)*珍珠 i 的价值 | j<i}

代码如下：

1 # include
     
       2 # include
      
        3 # include
       
         4 # define maxn 105 5 # define inf 100000000  //这个大小要合适，不然出错 6 using namespace std; 7  8 int dp[maxn],a[maxn],p[maxn];   //a[i]表示前i种珍珠的数量总和 9 int main()10 {11     int T,min,i,j,c;12     scanf("%d",&T);13     while(T--)14     {15         scanf("%d",&c);16         a[0] = 0;17         int temp;18         for(i=1; i<=c; i++)19         {20             scanf("%d%d",&temp,&p[i]);21             a[i] = a[i-1] + temp;22         }23         memset(dp,0,sizeof(dp));24         for(i=1; i<=c; i++)25         {26             min = inf;27             for(j=0; j