• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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.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?

            posted on 2010-03-13 16:24 schindlerlee 閱讀(1825) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久这里只有精品18| 亚洲国产精品综合久久网络| 久久婷婷五月综合色高清| 久久精品www人人爽人人| 久久噜噜电影你懂的| 久久久久国产精品麻豆AR影院| 中文字幕精品久久久久人妻| 日韩精品久久久久久久电影蜜臀| 蜜桃麻豆www久久| 久久综合亚洲色一区二区三区| 久久国产乱子伦免费精品| 亚洲国产精品成人久久蜜臀| 国产精品国色综合久久| 久久久久久曰本AV免费免费| 亚洲一区二区三区日本久久九| 久久这里只有精品首页| 久久久精品免费国产四虎| 亚洲AV成人无码久久精品老人| 国产精品伊人久久伊人电影 | 日本三级久久网| 久久国产劲爆AV内射—百度| 国产精品熟女福利久久AV| 丰满少妇人妻久久久久久| av色综合久久天堂av色综合在| 狠狠色伊人久久精品综合网| 99久久国语露脸精品国产| 久久亚洲国产精品成人AV秋霞| 精品久久久久久无码人妻热| 精品久久久久久无码专区不卡 | 天天综合久久一二三区| 色综合久久中文综合网| 99久久久国产精品免费无卡顿| 国产成人精品综合久久久久| 久久国产亚洲精品| 久久这里只精品99re66| 亚洲а∨天堂久久精品| 久久中文精品无码中文字幕| 久久有码中文字幕| 久久只这里是精品66| 无码伊人66久久大杳蕉网站谷歌| 久久伊人精品一区二区三区|