城市交通

jzoj 1749

題目大意

有n個點，x到y的前提是x<y,代價是$(y?x)?a_x+b_y$，問從1到n的最小代價是多少

輸入樣例

4 2 9 5 4 9 1 2 2

輸出樣例

8

數據范圍

對于20%的數據，$1?n?100；$
對于50%的數據，$1?n?3000；$
對于100%的數據，$1?n?100000，1?Ai,Bi?10^9。$

解題思路

y要大于x，就說明不能倒著走，那就可以用DP來做
我們設$f_i$為到從1到i的最小代價，如果我們直接枚舉從哪里來，那時間復雜度就是$o(n^2)$，那就會TLE
那我們考慮優化
我們可以用單調隊列來存有用的狀態
有用的狀態（i）對比前面所有有用的狀態（j）都必須滿足以下兩個條件之一
1:、$a_i<a_j$
2、$b_i<b_j$
這樣才可能使答案更優
后面的狀態只須從有用的狀態轉移
當然這樣還是可能被卡，但數據太水，A了

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n, w, p, a[100500], b[100500], f[100500], k[100500]; int main() {scanf("%lld", &n);for (ll i = 1; i <= n; ++i)scanf("%lld", &a[i]);for (ll i = 1; i <= n; ++i)scanf("%lld", &b[i]);memset(f, 127/3, sizeof(f));f[1] = 0;k[++w] = 1;//有用的狀態for (ll i = 2; i <= n; ++i){p = 1;for (int j = 1; j <= w; ++j){f[i] = min(f[i], f[k[j]] + a[k[j]] * (i - k[j]) + b[i]);//轉移if (a[i] > a[k[j]] && b[i] > b[k[j]]) p = 0;//判斷是否是有用的狀態}if (p)k[++w] = i;//加入}printf("%lld", f[n]);return 0; }

注：

這道題還可以用斜率優化做，但本蒟蒻還要學習學習

總結

以上是生活随笔為你收集整理的【单调队列】【DP】城市交通（jzoj 1749）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。