斜率优化

admin

留着

admin

题目描述
【题目描述】
有N (1 <= N <= 50,000) 块长方形的土地。每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000)。
每块土地的价格是它的面积，但FJ可以同时购买多块土地。这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换。
如果FJ买一块3×5的地和一块5×3的地，则他需要付5×5=25。
FJ希望买下所有的土地，但是他发现分组来买这些土地可以节省经费。
他需要你帮助他找到最小的经费。
【输入格式】
第1行一个整数N。
下来N行。第i+1行包含两个数，分别为第i块土地的长和宽。
【输出格式】
求最小的可行费用。
【样例输入】
4
100 1
15 15
20 5
1 100
【样例输出】
500
【样例解释】
FJ分3组买这些土地:
第一组:100×1,
第二组1×100,
第三组20×5 和 15×15。
每组的价格分别为100,100,300, 总共500

输入
输出
提示
来源
Usaco2008 Mar

admin

题目描述

【问题描述】
有N个工厂，由高到底分布在一座山上。工厂1在山顶，工厂N在山脚。
L公司一般把产品直接堆放在露天，以节省费用。
突然有一天，被告知三天之后将有一场暴雨，于是公司决定紧急在某些工厂建立一些仓库以免产品被淋坏。
对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，
产品只能往山下运（即只能运往编号更大的工厂的仓库），
当然运送产品也是需要费用的，假设一件产品运送1个单位距离的费用是1。
假设建立的仓库容量都都是足够大的，可以容下所有的产品。
你将得到以下数据：
1、工厂i距离工厂1的距离Xi（其中X1=0）;
2、工厂i目前已有成品数量Pi;
3、在工厂i建立仓库的费用Ci;
请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。
【输入文件】
第一行一个整数N，表示工厂的个数。
接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。
【输出文件】
输出一行一个整数，为可以找到最优方案的费用。
【样例输入】
3
0 5 10
5 3 100
9 6 10
【样例输出】
32
【样例说明】
在工厂1和工厂3建立仓库，建立费用为10+10=20，运输费用为(9-5)*3 = 12，总费用32。
如果仅在工厂3建立仓库，建立费用为10，运输费用为(9-0)*5+(9-5)*3=57，总费用67，不如前者优。
【数据规模】
对于20%的数据， N ≤500；
对于40%的数据， N ≤10000；
对于100%的数据， N ≤1000000。
所有的Xi, Pi, Ci均在32位带符号整数以内，保证中间计算结果不超过64位带符号整数。

输入
输出
提示
来源
ZJOI2007

admin

题目描述
【题意】
一个包装运输公司，只生产一种容量为L的包装盒。如果要装容量为X的物品，则需要花钱修改包装盒的尺寸，花费为（X - L）^2。
现在有N个物品需要装入包装盒，每个物品的容量为Ci。
（1）、可以多个物品装入一个包装盒
（2）、同一个包装盒的物品编号必须是连续的
（3）、同个包装盒的物品排成直线，相邻两个物品之间要加一块容量为1的隔板。
目标：总花费最小。

【输入格式】
第一行两个整数，分别为N和L。
下来N个数字Ci，按编号从小到大输入每个物品的容量。
1<=N<=50000,1<=L，Ci<=10^7
【输出格式】
一个整数，总花费的最小值。
【样例输入】
5 4
3 4 2 1 4
【样例输出】
1

输入
输出
提示

f[i]表示1~i的最小花费。

f[i]=min(f[j]+(sum[i]-sum[j]+i-(j+1)-L)^2) (j<i)

f[i]=min(f[j]+(sum[i]+i-sum[j]-j-1-L)^2) (j<i)

令s[i]=sum[i]+i,L=1+L

则f[i]=min(f[j]+(s[i]-s[j]-L)^2)



1.证明决策单调性

假设j1<j2<i,在状态i处的j2决策不比j1决策差（心里想着淘汰j1），

即要满足：f[j2]+(s[i]-s[j2]-L)^2<f[j1]+(s[i]-s[j1]-L)^2

则对于i后的所有状态t，是否j2也不比就j1差？（术语：证明决策单调性）

即f[j2]+(s[t]-s[j2]-L)^2 < f[j1]+(s[t]-s[j1]-L)^2

容易理解s[t]=s[i]+v

所以得到（1）不等式：f[j2]+(s[i]-s[j2]-L+v)^2<f[j1]+(s[i]-s[j1]-L+v)^2

因为已知（2）不等式：f[j2]+(s[i]-s[j2]-L  )^2<f[j1]+(s[i]-s[j1]-L  )^2

所以化简（1）不等式：把s[i]-s[j2]-L看成一个整体，v看成一个整体，得到

f[j2]+(s[i]-s[j2]-L  )^2 +2*v*(s[i]-s[j2]-L)+v^2 <f[j1]+(s[i]-s[j1]-L  )^2+2*v*(s[i]-s[j1]-L)+v^2

比较（2）不等式：

左边多了一部分：2*v*(s[i]-s[j2]-L)+v^2

右边多了一部分：2*v*(s[i]-s[j1]-L)+v^2

所以我们只需要证：

2*v*(s[i]-s[j2]-L)+v^2<=2*v*(s[i]-s[j1]-L)+v^2

即：(s[i]-s[j2]-L)    <=    (s[i]-s[j1]-L)

即：     -s[j2]       <=         -s[j1]

即：s[j1]<s[j2]这是肯定的，所以得证。

总结：对于当前i：j2比j1好，那么对于t(i<t)来说一样：j2一样比j1好，

所以当前i选择j2，淘汰j1，以后的t也不会在j2存在的时候选择j1，

所以i的时候就可以永久淘汰j1.



2.求斜率方程：

因为f[j2]+(s[i]-s[j2]-L)^2 < f[j1]+(s[i]-s[j1]-L)^2

展开:

f[j2]+(s[i]-L)^2-2*(s[i]-L)*s[j2]+s[j2]^2<f[j1]+(s[i]-L)^2-2*(s[i]-L)*s[j1]+s[j1]^2

即f[j2]-2*(s[i]-L)*s[j2]+s[j2]^2<f[j1]-2*(s[i]-L)*s[j1]+s[j1]^2

即f[j2]+s[j2]^2-2*(s[i]-L)*s[j2]<=f[j1]+s[j1]^2-2*(s[i]-L)*s[j1]

即[ (f[j2]+s[j2]^2)-(f[j1]+s[j1]^2) ] <  2*(s[i]-L)*s[j2]-2*(s[i]-L)*s[j1]

即[ (f[j2]+s[j2]^2)-(f[j1]+s[j1]^2) ] /(s[j2]-s[j1]) <  2*(s[i]-L)

对于j来说：

制造的点坐标

Y=f[j]+s[j]^2

X=s[j]



我们用队列list在存有意义的决策点，list中相邻两点的斜率递增（队列中的点形成一个下凸壳），而且都

大于2*(s[i]-L)，那么队列头对于i来说就是最优决策点。

加入决策i时，令队尾为list[tail]，前一个为list[tail-1]

斜率函数slop（点1，点2）

满足:  slop(list[tail-1],list[tail]) > slop(list[tail],i)  时，

那么队尾list[tail]在三者（list[tail-1],list[tail]，i）对于未来的t绝对不会是最优的策略，所以将

其弹出tail--;

最后遇到了：slop(list[tail-1],list[tail]) <  slop(list[tail],i),保证了队列的相邻两点的斜率递

增所以加入i： list[++tail]=i;