亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

bzoj 1096: [ZJOI2007]倉庫建設

系統 1736 0

? dp是很好想的了,關鍵是數據太大,普通dp肯定超時,所以一定有用某種優化,dp優化也就那么幾種,這道題用的是 斜率優化 ,先寫出普通的狀態轉移方程: dp[i] = min{ ?dp[j] + Σ ( p[k] * (x[i] - x[k] ) )?, ?j+1 <=k <= i , ?0 <= j <= i-1}

這個式子應該是很好理解的。接下來,就要進行優化。dp[j] 無法改變, 所以只好放眼于第二項, 即sigma那一項

Σ ( p[k] * (x[i] - x[k] ) =?Σ (p[k] * x[i] - p[k] * x[k]) = p[ j+1 ~ i] * x[i] - p[ j+1~i] * x[ j+1 ~i]

我們發現,這個式子中,x[i] 為當前點的量,而p[j+1 ~i] 和 p[j+1 ~i] * x[j+1 ~i] 很容易預處理得到。

于是,我們把 a[i] 定義為 到 i 為止所有貨物的個數 即 sum( p[1~i] ) ; 把b[i] 定義為到 i 為止 所有 p[j] * x[j] 之和

即 sum( p[ j+1~i] * x[ j+1 ~i]?) ;

我們有了這兩個預處理,就可以轉化成斜率優化來做了,一開始的式子,我們轉化為

dp[i] = min { dp[j] + x[i] * (a[i] - a[j]) - (b[i] - b[j]) }

剩下的就是斜率優化的內容了,這里不再贅述,注意一點, a[i] - a[j] 是負數 除過去要變號。

代碼如下

      #include <cstdio>
      
        

#include 
      
      <cstring>
      
        

#include 
      
      <cstdlib>
      
        

#include 
      
      <iostream>
      
        

#include 
      
      <algorithm>
      
        

#include 
      
      <queue>


      
        #define
      
       N 1000100


      
        using
      
      
        namespace
      
      
         std;

 


      
      
        int
      
      
         n;

deque
      
      <
      
        int
      
      >
      
         q;

deque
      
      <
      
        int
      
      >
      
        ::iterator x, y;


      
      
        long
      
      
        long
      
       a[N]={
      
        0
      
      }, b[N]={
      
        0
      
      
        };


      
      
        long
      
      
        long
      
      
         f[N], dis[N], c[N];

 


      
      
        long
      
      
        long
      
       getup(
      
        int
      
       j, 
      
        int
      
       k) { 
      
        return
      
       f[j] - f[k] + b[j] -
      
         b[k]; }


      
      
        long
      
      
        long
      
       getdown(
      
        int
      
       j, 
      
        int
      
       k) { 
      
        return
      
       a[j] -
      
         a[k]; }


      
      
        long
      
      
        long
      
       getans(
      
        int
      
       j, 
      
        int
      
       now) { 
      
        return
      
       f[j] + (a[now] - a[j]) * dis[now] -b[now] + b[j] +
      
        c[now]; }


      
      
        bool
      
       ketan(
      
        int
      
       j, 
      
        int
      
       k, 
      
        int
      
       now) { 
      
        return
      
       getup(j, k) < dis[now] *
      
         getdown(j, k); }


      
      
        bool
      
       keya(
      
        int
      
       i, 
      
        int
      
       j, 
      
        int
      
       k) { 
      
        return
      
       getup(i, j) * getdown (j, k) > getup(j, k) *
      
         getdown(i, j); }

 


      
      
        int
      
      
         main()

{

    scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        n);

    
      
      
        for
      
       (
      
        int
      
       i = 
      
        1
      
      ; i <= n; ++
      
        i)

    {

        
      
      
        long
      
      
        long
      
      
         z;

        scanf(
      
      
        "
      
      
        %lld%lld%lld
      
      
        "
      
      , &dis[i], &z, &
      
        c[i]);

        a[i] 
      
      = a[i-
      
        1
      
      ] + z; b[i] = b[i-
      
        1
      
      ] + z*
      
        dis[i];

    }

    f[
      
      
        0
      
      ] = 
      
        0
      
      ; q.push_front(
      
        0
      
      
        );

    
      
      
        for
      
       (
      
        int
      
       i = 
      
        1
      
      ; i <= n; ++
      
        i)

    {

        
      
      
        while
      
       (q.size() > 
      
        1
      
      
        )

        {

            x 
      
      = q.begin(); y = x; y++
      
        ;

            
      
      
        if
      
       (!ketan(*y, *x, i)) 
      
        break
      
      
        ;

            q.pop_front();

        }

        x 
      
      =
      
         q.begin();

        f[i] 
      
      = getans(*
      
        x, i);

        
      
      
        while
      
       (q.size() > 
      
        1
      
      
        )

        {

            x 
      
      = q.end(); x--; y = x; y--
      
        ;

            
      
      
        if
      
       (!keya(*y, *x, i)) 
      
        break
      
      
        ;

            q.pop_back();

        }

        q.push_back(i);

    }

    printf(
      
      
        "
      
      
        %lld\n
      
      
        "
      
      
        , f[n]);

}
      
    

?

bzoj 1096: [ZJOI2007]倉庫建設


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久国产大片 | 欧美成人在线视频 | 99久久精品国产亚洲 | 国内精品久久久久久 | 欧美精品在线播放 | 伦理一区 | 亚洲 欧美 国产 中文 | 国产精品久久天天影视 | 亚洲精品成人 | www.天天操.com| 久久永久免费中文字幕 | 97国产免费全部免费观看 | 射狠狠| 99久久精品久久久 | 国产免费福利 | 日韩亚洲欧洲在线rrrr片 | 狠狠色噜噜狠狠狠狠888奇米 | 99视频在线播放 | 欧美成人aaaaa免费视频 | 欧美理论在线 | 色中色污| 99国产精品久久久久久久... | 99热精品在线观看 | 97精品一区二区三区在线不卡 | 亚洲性一级理论片在线观看 | 欧美xxx网站 | 久久久久国产精品美女毛片 | 996热精品视频在线观看 | 操你妹影院 | 国产午夜亚洲精品久久www | 欧美成人性做爰 | 我就色色综合网 | 亚洲一区二区三区视频 | 四虎国产精品永久地址51 | 四虎欧美 | 九九在线精品视频播放 | 久久久久国产精品免费看 | 中文字幕亚洲第一 | 可以免费观看欧美一级毛片 | 国产亚洲精品网站 | 日本精品夜色视频一区二区 |