【poj1260】 Pearls

http://poj.org/problem?id=1260 (题目链接)

题意

　　购买珍珠，所有珍珠分成n个档次，第i个档次购买每个珍珠的价格为p[i]，需要购买第i档次的珍珠a[i]个。若要购买第i组珍珠，则所需要支付的价格为：(a[i]+10)*p[i]，也就是说购买每组价格不同的珍珠所需要多支付10个珍珠的价格。可以用档次高的珠宝来替代档次低的珠宝。这样或许可以节省总钱数。而题目就是要求出购买所有数量的珠宝所需支付的最低价格。

Solution

　　决策单调性证明+斜率优化，如果要证明的话，套路与玩具装箱差不多，反正就是证了单调性后化成斜率式搞一下。于是我们默认它具有决策单调性，然后拿单调性那个式子玩出斜率式，写个暴力拍一下就OK。

细节

　　原来档次高的珠宝不一定价格就贵mdzz，一开始所以不用按照价格排序，贡献1Wa。

代码

// poj1260

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483600

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=200;

struct data {int a,p;}t[maxn];

int f[maxn],s[maxn],q[maxn];

int n;

double K(int a,int b) {

	return (double)(f[a]-f[b])/(double)(s[a]-s[b]);

}

bool cmp(data a,data b) {

	return a.p<b.p;

}

int main() {

	int T;scanf("%d",&T);

	while (T--) {

		scanf("%d",&n);

		for (int i=1;i<=n;i++) scanf("%d%d",&t[i].a,&t[i].p);

		//sort(t+1,t+1+n,cmp);

		for (int i=1;i<=n;i++) s[i]=s[i-1]+t[i].a;

		int l=1,r=1;q[1]=0;

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

			while (l<r && K(q[l],q[l+1])<=(double)t[i].p) l++;

			f[i]=f[q[l]]+(s[i]-s[q[l]]+10)*t[i].p;

			while (l<r && K(q[r-1],q[r])>K(q[r],i)) r--;

			q[++r]=i;

		}

		printf("%d\n",f[n]);

	}

    return 0;

}