2010年03月13日星期六.sgu148.B-station 利用单调性优化dp 思考啊思考
heap + dp
题目描述：给出n层大坝，每层的现有水量，能储水量，炸毁所需的价格，求炸掉最后一层需要花费
的最小费用时的需要炸毁哪些层。
如果第i层被炸毁那么这层的水就会流到下一层，如果大于能储水量，那么这层就也被冲毁。
首先想一个朴素的想法，枚举炸哪一层
for(int i = 1;i <= n;i++) {
int cost = price[i],flow = w[i];
for(int j = i + 1;j <= n;j++) {
flow += w[j];
if(flow <= L[j]) {
cost += price[j];
}
}
if (ans > cost) {
ans = cost;
}
}
显然n = 15000,O(n^2)会超时。
观察到如果第i层被冲开之后，i+1...n中所有能被累计的水冲毁的那么1...i-1都会被自然冲开，
所以不用再被计算。
然后如果现在处理的是i点
如果 sum[i] - sum[idx] - (L[idx] - w[idx]) > 0 其中 sum[i]表示Σw[i...n]
那么 idx就能被累计的水冲开。
由于 - sum[idx] - (L[idx] - w[idx]) 是固定的，所以就可以利用堆来做
注意//!!地方的语句，这道题就是思考。nlogn 47ms
1
2 const int N = 15100;
3 int w[N], L[N], p[N], n;
4 int sum[N];
5
6 struct T {
7 int need, idx;
8 T() {
9 } T(int a, int b) {
10 need = a, idx = b;
11 }
12 };
13
14 bool operator <(T a,T b)
15 { return -a.need < -b.need; }
16 //http://www.cppblog.com/schindlerlee
17 void proc()
18 {
19 int i, j, k;
20 priority_queue < T > que;
21 for (i = n; i >= 1; i--) {
22 sum[i] = sum[i + 1] + w[i];
23 }
24 int ans = maxint, cost = 0, idx;
25 for (i = n; i >= 1; i--) {
26 cost += p[i];
27 while (!que.empty() && sum[i] - que.top().need > 0) { //!!
28 cost -= p[que.top().idx];
29 que.pop();
30 }
31 que.push(T(L[i] - w[i] + sum[i], i)); //!!
32 if (ans > cost) {
33 ans = cost;
34 idx = i;
35 }
36 }
37
38 cost = 0;
39 for (i = idx; i <= n; i++) {
40 cost += w[i];
41 if (cost <= L[i]) {
42 printf("%d\n", i);
43 }
44 }
45 }
46
47 int main()
48 {
49 int i, j, k;
50 scanf("%d", &n);
51 for (i = 1; i <= n; i++) {
52 scanf("%d %d %d", w + i, L + i, p + i);
53 }
54 proc();
55 return 0;
56 }
57