Pb的生日蛋糕
原题：（权限限制没有超链接）
题目描述Description
Pb的好朋友的生日就要到了，Pb决定给他送一个自己做的生日蛋糕。
现在Pb手里拥有一些圆柱形蛋糕，他想将他们组合起来做成一个大的生日蛋糕，也就是将一些圆柱形蛋糕堆放在另一些上面。每个蛋糕现在都有一个底面半径，高和美味度。Pb规定堆放在上层的蛋糕的美味度和体积都必须严格大于下层的蛋糕。并且我们约定没有任何两个蛋糕的美味度相同。
Pb现在会按美味度由小到大的顺序给你每个蛋糕的半径和高，他想知道他所能堆出的生日蛋糕体积最大为多少？注意到蛋糕的美味度具体是多少对我们没有任何影响。
输入描述Input Description
第一行一个整数N，表示Pb有多少个蛋糕
接下来N行，每行两个整数，表示每个蛋糕的半径和高。
输入顺序即为蛋糕美味度由小到大的顺序。
输出描述Output Description
输出一个浮点数，表示最大体积。如果你的答案和标准答案的误差不超过10^−3则认为你的答案是正确的。保证标准答案输出9位小数。
样例输入Sample Input
样例输入1：
2
100 30
40 10
样例输入2：
4
1 1
9 7
1 4
10 7
样例输出Sample Output
样例输出1：
942477.796077000
样例输出2：
3983.539484752
数据范围及提示Data Size & Hint
此题共4个子任务，你只有通过一个子任务中的所有测试点，才能得到该子任务的分值。
子任务1:9分，保证N<=10。
子任务2:19分，保证N<=1000。
子任务3:22分，保证r,h<=100。
子任务4:50分，无特殊约定。
对于所有测试数据，保证N<=100000, r,h<=10000。
个人解法：
首先，我们可以很容易想到朴素的算法——DP。用f[i]表示当前以i为顶端的最大体积，那么我们很容易得出f[i]=max(f[j])+v[i]，其中1<=j<=i-1,v[j]<v[i]。
可是i与j的规模都达到了100000，O(n^2)的算法显然超时。
有趣的是，子任务3给了我们一点提示。
我们发现，每一次DP我们都是找到在当前i之前的最大的f[j]，有没有什么可以优化一下这一循环呢？答案是肯定的。
我们可以以v[i]作为下标构造一个数组a。在每一次DP完之后就把f[i]扔到这个以v[i]为下标的数组里。那么我们得到的这一个数组中，就是i之前的所有f[i]的值。接下来我们找最大值就方便多了。我们知道当前的v[i]，所以我们只需要在a[1]-a[v[i]-1]的所有f[i]中找到最大的一个f[i]，这用树状数组、线段树等诸如此类者都可以。
最后的答案就是a[1]-a[max(v[i])]的最大f[i]。
当然，由于r,h的规模达到了10000，也就意味着v[i]规模达到了10^12。又由于我们只需要体积的大小顺序就可，因此用离散化把v缩小到n的规模。
代码如下：
type
arr110000=array[0..110000] of int64;
var
f,v,p,b,c:arr110000;//f在之前是离散数组，之后是DP数组。v是体积，p、b是离散数组，c是树状数组
r,h,j:int64;
n,i:longint;
s:double;
function lowbit(x:longint):longint;//树状数组函数
begin
exit(x and (-x));
end;
function max(a,b:int64):int64;//较大值
begin
if a>b then exit(a);
exit(b);
end;
procedure change(i:longint;data:int64);//修改
begin
while i<=n do
begin
c[i]:=max(c[i],data);
inc(i,lowbit(i));
end;
end;
function getsum(i:longint):int64;//统计1到i的最大值
begin
getsum:=0;
while i>0 do
begin
getsum:=max(getsum,c[i]);
dec(i,lowbit(i));
end;
end;
procedure swap(var a,b:int64);//交换+排序
var
c:int64;
begin
c:=a;
a:=b;
b:=c;
end;
procedure sort(l,r:longint);
var
tl,tr:longint;
m:int64;
begin
tl:=l;
tr:=r;
m:=f[(tl+tr) shr 1];
repeat
while f[tl]<m do inc(tl);
while f[tr]>m do dec(tr);
if tl<=tr then
begin
swap(f[tl],f[tr]);
swap(b[tl],b[tr]);
inc(tl);
dec(tr);
end;
until tl>tr;
if tl<r then sort(tl,r);
if l<tr then sort(l,tr);
end;
begin
read(n);
for i:=1 to n do
begin
read(r,h);
v[i]:=r*r*h;//数据处理
f[i]:=v[i];
end;
for i:=1 to n do
b[i]:=i;
sort(1,n);//排序离散
p[b[1]]:=1;
for i:=2 to n do
if v[b[i]]>v[b[i-1]] then p[b[i]]:=p[b[i-1]]+1//下标离散
else p[b[i]]:=p[b[i-1]];
fillchar(f,sizeof(f),0);
for i:=1 to n do
begin
j:=getsum(p[i]-1);//取出1-p[i]-1中的最大的f[j]
f[i]:=j+v[i];//计算当前f[i]
change(p[i],f[i]);//把f[i]放入树状数组
end;
j:=getsum(n);//统计答案
s:=j*pi;
writeln(s:0:9);
end.
受益匪浅。第一次接触到了除了四边形不等式以外的DP加速方法。这么说来还有许多强有力的优化呢。
如果有什么优化，希望各位大神提出。
DP路上，希望与你们共同进步。