? 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]); }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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