2010年03月13日星期六.sgu148.B-station 利用單調(diào)性優(yōu)化dp 思考啊思考
heap + dp
題目描述：給出n層大壩，每層的現(xiàn)有水量，能儲(chǔ)水量，炸毀所需的價(jià)格，求炸掉最后一層需要花費(fèi)
的最小費(fèi)用時(shí)的需要炸毀哪些層。
如果第i層被炸毀那么這層的水就會(huì)流到下一層，如果大于能儲(chǔ)水量，那么這層就也被沖毀。
首先想一個(gè)樸素的想法，枚舉炸哪一層
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)會(huì)超時(shí)。
觀察到如果第i層被沖開之后，i+1...n中所有能被累計(jì)的水沖毀的那么1...i-1都會(huì)被自然沖開，
所以不用再被計(jì)算。
然后如果現(xiàn)在處理的是i點(diǎn)
如果 sum[i] - sum[idx] - (L[idx] - w[idx]) > 0 其中 sum[i]表示Σw[i...n]
那么 idx就能被累計(jì)的水沖開。
由于 - 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://m.shnenglu.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?