Why so serious? --[NKU]schindlerlee

2010年03月13日星期六.sgu148. 利用单调性优化dp 思考啊思考

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 

posted on 2010-03-13 16:24 schindlerlee 阅读(1808) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理