? dp是很好想的了，關(guān)鍵是數(shù)據(jù)太大，普通dp肯定超時，所以一定有用某種優(yōu)化，dp優(yōu)化也就那么幾種，這道題用的是 斜率優(yōu)化 ，先寫出普通的狀態(tài)轉(zhuǎn)移方程： dp[i] = min{ ?dp[j] + Σ ( p[k] * (x[i] - x[k] ) )?, ?j+1 <=k <= i , ?0 <= j <= i-1}
這個式子應(yīng)該是很好理解的。接下來，就要進行優(yōu)化。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]
我們發(fā)現(xiàn)，這個式子中，x[i] 為當(dāng)前點的量，而p[j+1 ~i] 和 p[j+1 ~i] * x[j+1 ~i] 很容易預(yù)處理得到。
于是，我們把 a[i] 定義為 到 i 為止所有貨物的個數(shù) 即 sum( p[1~i] ) ； 把b[i] 定義為到 i 為止 所有 p[j] * x[j] 之和
即 sum( p[ j+1~i] * x[ j+1 ~i]?) ；
我們有了這兩個預(yù)處理，就可以轉(zhuǎn)化成斜率優(yōu)化來做了，一開始的式子，我們轉(zhuǎn)化為
dp[i] = min { dp[j] + x[i] * (a[i] - a[j]) - (b[i] - b[j]) }
剩下的就是斜率優(yōu)化的內(nèi)容了，這里不再贅述，注意一點， a[i] - a[j] 是負(fù)數(shù) 除過去要變號。
代碼如下
#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]);
}
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
