题意

　　有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
     
      #include
      
       #define N 105using 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
      
     

还有一种写法

#include
     
      #include
      
       #define N 105using 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;}