题目大意：珠宝店有许多珠宝，你需要每种珠宝各买一定的数目，各种珠宝的价格是不一样的，每种珠宝买的时候都必须多付10颗该珠宝的钱，但一种珠宝可以用比它更贵的珠宝来代替，所以有时候用更贵的珠宝来充数可能更省钱。现在问你最少要多少钱？输入数据已按珠宝按价格升序排序。
分析：开始想的时候想了一个二维的方程，但是一维就够了。设f[i]表示买了第i种珠宝，前面的珠宝都已经买了或有更贵的充数，此时所花的最少的钱。
则f[i]=min(f[k]+(sum[i]-sum[k]+10)*price[i])
设y=f[k]+sum[i]*price+10*price,x=sum[k],b=prixe[i],g=f[i],则上式变为：g=y-bx
b是递增的，所以有效决策点满足下凸包性质。
这道题我居然把一处Y(j)写成了(j),WA了许多次，真是够了。粗心害死人，一定要细心一点。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 105
int f[MAXN],w[MAXN],sum[MAXN],que[MAXN],head,tail,last;
struct zhu
{
int sum,w;
}arr[MAXN];
int X(int i)
{
return arr[i].sum;
}
int Y(int i)
{return f[i];
}
bool turnup(int i,int j,int k)
{
if((X(j)-X(k))*(long long)(Y(i)-Y(j))>(X(i)-X(j))*(long long)(Y(j)-Y(k)))
return ;
else return ;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
head=tail=;
last=;
que[tail++]=;
f[]=;
arr[].sum=,arr[].w=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{scanf("%d %d",&arr[i].sum,&arr[i].w);
arr[i].sum+=arr[i-].sum;
}
for(int i=;i<=n;i++)
{
while(head<tail-&&Y(que[head+])-Y(que[head])<=arr[i].w*(long long)(X(que[head+])-X(que[head])))
head++;
int best=que[head];
f[i]=f[best]+(arr[i].sum-arr[best].sum+)*(long long)arr[i].w;
while(head<tail-&&turnup(i,que[tail-],que[tail-])==)
tail--;
que[tail++]=i;
}
printf("%d\n",f[n]);
}
}