題目

        在離著名的國(guó)家Berland不遠(yuǎn)的地方，有一個(gè)水下工作站。這個(gè)工作站有N層。已知：是第層裝有Wi的水，最多可以容納Li的水，恐怖分子炸毀第i的代價(jià)是Pi。第i層一旦被炸毀，該層所有的水都將傾瀉到第i+1層。如果某一層的水量超過(guò)了它的容量(即Li)，那么該層就將自動(dòng)被毀壞，所有的水也會(huì)傾瀉到下一層。

        Pivland的恐怖分子想要用最少的錢毀掉第N層，現(xiàn)在他雇傭你來(lái)計(jì)算，需要炸毀哪些層。

輸入

      第一行有一個(gè)自然數(shù)N(1<=n<=15000)。接下來(lái)的N行，每行3個(gè)整數(shù)Wi, Li, Pi(0<=Wi,Li,Pi<=15000)。

輸出

     輸出需要炸毀的層的編號(hào)。

Solution1：小根堆+枚舉。

從下往上推的話，f[i]是從i層開始炸毀的代價(jià)如果炸毀i-1，且s[i]-s[i-2]>l[i],那么從第i-1層開始炸毀的代價(jià)是f[i]+c[i-1]-c[i]; 從第k層開始炸毀時(shí)只要將第i(k<i<=n)層里（s[i]-s[k-1]>l[i]) 層里之前算作炸毀的層的c[i]減去,并標(biāo)記沒(méi)被炸毀.用優(yōu)先隊(duì)列優(yōu)化的話將快很多,只要將當(dāng)前炸毀的層入隊(duì),當(dāng)滿足s[i]-s[k-1]>l[i]時(shí),出隊(duì)并減去c[i];

#include <cstdio>  #include <queue>  #include <utility>  using namespace std;  typedef pair<int,int> aii;const int maxx = 15000+10, INF = 2e9;  PRiority_queue< aii > heap;int n;int ans = INF,flag = 0,sum = 0,Sum = 0; int v[maxx],s[maxx],c[maxx];int pre[maxx];bool hash[maxx];int main()   {  //	freopen("Bstation.in","r",stdin);//	freopen("Bstation.out","w",stdout);	    scanf("%d",&n);      	for(int i=n;i>=1;i--)       {          scanf("%d%d%d",&s[i],&v[i],&c[i]);            pre[i] = pre[i+1]+s[i];      }       	for(int i=1;i<=n;i++)      {          for(;!heap.empty() && heap.top().first>pre[i+1]; heap.pop())              sum -= heap.top().second;        heap.push(make_pair(pre[i]-v[i], c[i]));          sum+=c[i];          if(ans>sum)          {              ans = sum;              flag = i;             }      }        	for(int i=flag;i>=1;i--)      {          Sum += s[i];        if(Sum>v[i])              hash[i] = true;       }          for(int i=flag;i>=1;i--)          if(!hash[i])              printf("%d/n", n-i+1);      return 0;  }Solution2：類似二分查找的算法。
之前做過(guò)B-station，是用堆的方法。奈何考場(chǎng)碰到此題時(shí)早已把此方法忘得一干二凈/捂臉。所以迫不得已，強(qiáng)行自己創(chuàng)造了
一個(gè)類似二分查找的方法來(lái)通過(guò)此題防止爆零…咳咳咳，這個(gè)方法大致是這樣的。讀入時(shí)首先處理（由于本人個(gè)人習(xí)慣原因，把最高
層叫做第一層。要炸的叫最底層）之后用sum[i]表示重量的前綴和，用val[i]表示炸該層的費(fèi)用。之后把每層放入結(jié)構(gòu)體。關(guān)鍵字：
d，l，w，id，need（need保存的是壓毀此層時(shí)至少毀掉的最高層。換句話說(shuō)，設(shè)i層的need為need[i]，只要從need[i]到i-1之間
所有層都已毀壞，第i層就會(huì)直接被壓毀。而這個(gè)need怎么求呢？假設(shè)第i層的need[i]為T，則有sum[i]-sum[T-1]>l[i]。經(jīng)變形得
到sum[T-1]<sum[i]-l[i]。這時(shí)候，因?yàn)閟um單調(diào)遞增，可知sum[T]>=sum[i]-l[i]。所以可以用lower_bound函數(shù)直接找出
need[i]。接下來(lái)我們要做的是將結(jié)構(gòu)體依照need進(jìn)行排序。然后創(chuàng)建一個(gè)vector<int> sale[]的數(shù)組。sale[i]中存以此層作為最
高層時(shí)可以壓毀的層的編號(hào)。之后就直接自底往上開始枚舉最高層。每次枚舉時(shí)首先tmp += val[i]（都考慮直接炸掉），之后在
sale[i]中進(jìn)行查找，如果有編號(hào)在i層和底層之間，也就是sale[i][j]>i，則tmp-=val[sale[i][j]]。（說(shuō)明以i為最高層時(shí)此層不用
炸）。每次枚舉過(guò)后比較tmp與Ans。最終就能得到答案。//考試時(shí)做了幾個(gè)小時(shí)，生無(wú)可戀.jpg。
#include <cstdio>#include <algorithm>#include <queue>#include <vector>using namespace std;const int maxx = 100000 + 100;struct Edge{    int id;    int d;    int l;    int w;    int need;}Edges[maxx];long long sum[maxx],val[maxx],cost[maxx];long long Ans = 1e9 + 100,tmp;int n;vector <int> sale[maxx];bool cmp(Edge a,Edge b){    if(a.need != b.need)    return a.need<b.need;    else    return a.id<b.id;}int main(){//    freopen("Bomb.in","r",stdin);//    freopen("Bomb.out","w",stdout);        scanf("%d",&n);        for(int i=n;i>=1;i--){        scanf("%d%d%d",&Edges[i].d,&Edges[i].w,&Edges[i].l);        val[i]=Edges[i].d;        Edges[i].id = i;    }        for(int i=1;i<=n;i++)        sum[i]=sum[i-1]+Edges[i].w;        for(int i=1;i<=n;i++){        int T = lower_bound(sum,sum+i,sum[i]-Edges[i].l)-sum;        if(T>0) Edges[i].need = T;        else Edges[i].need = 0;    }        sort(Edges+1,Edges+n+1,cmp);        for(int i=1;i<=n;i++)        sale[Edges[i].need].push_back(Edges[i].id);        for(int i=n;i>=1;i--){        tmp += val[i];        for(int j=0;j<sale[i].size();j++){            if(sale[i][j]>i)            tmp -= val[sale[i][j]];        }        Ans = min(Ans,tmp);    }    printf("%d",Ans);    return 0;}看來(lái)做過(guò)的題目還是要好好學(xué)懂啊QvQ。