P5785 SDOI2012 任務安排 斜率優化

2022-09-22 21:54:58 字數 1437 閱讀 7206

戳這裡

設 \(f[i][j]\) 表示列舉到第 \(i\) 個點,分成 \(j\) 段時的最小代價,

\(f[i][j]=min(f[k][j-1]+(s*j+sumt[i]-sumt[k])*(sumc[i]-sumc[k]))\)

然後用李超樹維護轉移,複雜度 \(o(n^2\log n)\)

在 巨佬 的提示下發現可以優化 dp 狀態,我們發現 dp 狀態的第二維可以通過更改列舉狀態優化掉,因為他在轉移式中只出現了一次,而且與 \(k\) 無關

我們設 \(f[i]\) 表示列舉到第 \(i\) 個點,之後的每一個點已經加上了由於之前重啟操作帶來的代價,轉移式就變為了

\(f[i]=min(f[j]+s*(sumc[n]-sumc[j])+sumt[i]*(sumc[i]-sumc[j]))\)

這樣把之後每一個點由於之前操作帶來的影響都消掉了

然後我們發現這個式子長的很斜率優化

我們令 \(k< j\) 且 \(j\) 比 \(k\) 轉移更優,那麼存在

\(f[j]+s*(sumc[n]-sumc[j])+sumt[i]*(sumc[i]-sumc[j])

化簡得到

\(f[j]-s*sumc[j]-sumt[i]*sumc[j]

\(\large\frac

但是關鍵在於 \(|t_i|<2^8\) ,也就是說 \(sumt[i]\) 並不單調,所以我們不能單調佇列維護,我們只能維護一個下凸殼,然後每次二分尋找最優決策點轉移

複雜度 \(o(n\log n)\)

#include#define pii pair#define mk(x,y) make_pair(x,y)

#define lc rt<<1

#define rc rt<<1|1

#define pb push_back

#define fir first

#define sec second

using namespace std;

namespace zzc

while (isdigit(ch))

return x*f; }

const int maxn = 3e5+5;

long long n,s,l,r;

long long f[maxn],c[maxn],ti[maxn],prec[maxn],pret[maxn],q[maxn];

long long upn(int j,int k)

long long dwn(int j,int k)

int solve(long long x)

return res==-1?q[r]:q[res]; }

void work()

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

int main()

P5785 SDOI2012 任務安排

本篇題解將分為四塊,一步一步地講解本題, n 3 演算法應該非常的顯然,我們設 f 為到 i 個任務,分為 j 個批次所使用的最少時間,易得轉移方程為 begin f min f sumt i s j suma i suna k 0 le k 但是這個複雜很明顯是過不了的 o n 2 都過不了,這還想...