SGU 148 解题手记
　　最朴素的，用c[k,v]表示淹掉第k层，且能够给第k+1层灌进v重量的水要花的钱：c[k,v]=min{ P(k)|(if W(k)>=v) , c[k-1,max{v,L(k)+1}-W(k)] }。最后所求是c[N,0]。但这样做空间尚且可以解决，无奈时间复杂度太大了。
　　但暂时想不到好办法，拿这个试一试吧。
　　不行，没办法记录决策。
　　发现有人写过《SGU 148 解题报告》，而且讲的已经非常清楚了。我对它有所修改，因为原文的Wi被定义了两次。
　　Submit 1: WA on 2。n=1的时候没处理。
　　Submit 2: WA on 5。编码上有点问题，B被pop成空集之后没有处理。
　　Submit 3: WA on 5。出这种错误真是太无语了，建堆的时候居然用Si作为key……应该用Ci。
　　Submit 4: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
 
struct lev
{
    int id,C,S,P;
};
 
bool operator <(const lev& a,const lev& b)
{
    return a.C<b.C;
}
 
int main()
{
    lev levels[15001]; levels[0].S=0;
    priority_queue<lev> B,minB;
    int n,cost(0),mincost(225000001);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        levels[i].id=i;
        int w,l;
        scanf("%d%d%d",&w,&l,&levels[i].P);
        levels[i].S=levels[i-1].S+w;
        levels[i].C=levels[i].S-l;
    }
    for (int i=n;i>=1;i--)
    {
        while (B.size() && B.top().C>levels[i-1].S)
        {
            cost-=B.top().P;
            B.pop();
        }
        B.push(levels[i]); cost+=levels[i].P;
        if (cost<mincost)
        {
            mincost=cost; minB=B;
        }
    }
    while (!minB.empty())
    {
        printf("%d\n",minB.top().id);
        minB.pop();
    }
    return 0;
}