题目链接：
题意：在离著名的国家Berland不远的地方，有一个水下工作站。这个工作站有N层。已知：是第i层装有Wi的水，最多可以容纳Li的水，恐怖分子炸毁第i层的代价是Pi。第i层一旦被炸毁，该层所有的水都将倾泻到第i+1层。如果某一层的水量超过了它的容量(即Li)，那么该层就将自动被毁坏，所有的水也会倾泻到下一层。Pivland的恐怖分子想要用最少的钱毁掉第N层，现在他雇佣你来计算，需要炸毁哪些层。
思路：令Si=W1+W2+…+Wi（特别的，S0=0）。不妨设恐怖分子炸毁的第高层是第p层（第一层是最高层，第N层是最底层）。因为恐怖分子的目标是毁灭第N层，所以水必须从第p层一直泻下去。如果存在一个i(i>p)，满足Wp+Wp+1+…+Wi-1+Wi<=Li，也就是说前面几层的水全部泄下来也无法把第i层自动冲毁，那么就必须要把它炸开了。所以恐怖分子需要炸毁的层的集合就是Bomb[p]={p}∪{i |i>p Si-Sp-1<=Li}。令Wi=Si-Li，那么：Bomb[p]={p}∪{i |i>p Wi<=Sp-1}。因此枚举p，然后看哪些层需要炸毁。这样就得到了一个O(n2)的算法。
注意到Sp是随着p的增加而递增的，观察两个集合：
Bomb[p]={p}∪{i |i>p Wi<=Sp-1}
Bomb[p-1]={p-1}∪{i |i>p-1 Wi<=Sp-2}
因为Sp-2<=Sp-1，所以{i |i>p-1 Wi<=Sp-2}Bomb[p]。
也就是说，Bomb[p-1]是在Bomb[p]的基础上，通过以下操作得到的：
1． 删除所有的i∈Bomb[p]，Wi>Sp-2。
2． 添加p-1。
针对这两种操作，我们可以使用大根堆(Heap)。从大到小枚举p，对于每一个p，执行：
Step1. 如果堆的根>Sp-1，那么删除根；否则转Step3。
Step2. 转Step1。
Step3. 添加p，同时更新答案。
1 struct node 2 { 3 int w,id; 4 5 node(){} 6 node(int _w,int _id) 7 { 8 w=_w; 9 id=_id;10 }11 };12 13 const int INF=1000000000;14 const int MAX=15005;15 int n,W[MAX],L[MAX],P[MAX],aSize;16 int S[MAX];17 node a[MAX<<2];18 19 void down(int t)20 {21 int L,R,k;22 while(1)23 {24 L=t*2;25 R=t*2+1;26 if(L<=aSize&&a[L].w>a[t].w) k=L;27 else k=t;28 if(R<=aSize&&a[R].w>a[k].w) k=R;29 if(k==t) break;30 swap(a[k],a[t]);31 t=k;32 }33 }34 35 void up(int t)36 {37 int p=t/2;38 while(p>=1)39 {40 if(a[p].w 0&&a[1].w>S[p-1])67 {68 cur-=P[a[1].id];69 a[1]=a[aSize--];70 down(1);71 }72 a[++aSize]=node(W[p],p);73 up(aSize);74 cur+=P[p];75 ans=min(ans,cur);76 }77 aSize=0;78 int tempAns=INF;79 cur=0;80 DOW1(p,n)81 {82 while(aSize>0&&a[1].w>S[p-1])83 {84 cur-=P[a[1].id];85 a[1]=a[aSize--];86 down(1);87 }88 a[++aSize]=node(W[p],p);89 up(aSize);90 cur+=P[p];91 tempAns=min(tempAns,cur);92 if(tempAns==ans) break;93 }94 sort(a+1,a+aSize+1,cmp);95 FOR1(i,aSize) PR(a[i].id);96 return 0;97 }