JZOJ 3432. 【GDOI2014模拟】伺服器

Problem

Description

我們需要将一個檔案複制到n個伺服器上，這些伺服器的編号為S1, S2, …, Sn。

首先，我們可以選擇一些伺服器，直接把檔案複制到它們中；将檔案複制到伺服器Si上，需要花費ci > 0的置放費用。對于沒有直接被複制檔案的伺服器Si來說，它依次向後檢查Si+1, Si+2, …直到找到一台伺服器Sj：Sj中的檔案是通過直接複制得到的，于是Si從Sj處間接複制得到該檔案，這種複制方式的讀取費用是j – i（注意j>i）。另外，Sn中的檔案必須是通過直接複制得到的，因為它不可能間接的通過别的伺服器進行複制。我們設計一種複制方案，即對每一台伺服器确定它是通過直接還是間接的方式進行複制（Sn隻能通過直接方式），最終使每一台伺服器都得到檔案，且總花費最小。

Input

輸入檔案的第一行有一個整數n，表示伺服器的數目。輸入檔案的第二行有n個整數，順數第i個表示ci：在Si上直接複制檔案的費用。

Output

輸出檔案中隻包含一個整數，即最少需要花費的費用。

Sample Input

10

2 3 1 5 4 5 6 3 1 2

Sample Output

18

Data Constraint

60%的資料中，1 <= n <= 1 000

100%的資料中，1 <= n <= 1 000 000

80%的資料中， 1 <= ci <= 50

100%的資料中，1 <= ci <= 1 000 000 000

最終結果可能較大，請注意選擇适當的資料類型進行計算。

Hint

Solution

向後往前遞推

60分方法

設F[i]表示i點直接複制，且右邊的所有點已處理完的最小費用。依題意得：

F[i]=min(F[j]+(j−i)(j−i+1)2)

時間複雜度：O(n^2)

100分算法

方法：斜率優化

如果有兩個點j,k，設j比k更優，則有

F[j]+(j−i)(j−i+1)2+a[i]<F[k]+(k−i)(k−i+1)2+a[i]

移項，整理，得

2F[j]−2F[k]+j2−k2−j+k)2(j−k)<i

我們建立一個隊列D，裡面的數量關系如下：

d[1]>d[2]>d[3]>….

設xl(j,k)=2F[j]−2F[k]+j2−k2−j+k)2(j−k)

則我們要把大于i的xl(j,k)統統踢掉，然後将i放入隊列。但是一定要保證i暫時是最小的，是以要将隊尾的大于i的xl(j,k)統統踢掉。

那麼問題來了，為什麼要從n-1 downto 0？（看下面的code）因為有的情況是1号伺服器不直接複制，且即使1号伺服器直接複制，f[1]=f[0]，是以用0代表第0号直接複制。因而遞推到0，輸出f[0].

我講得不是很好，因為我還是新手，敵不過老司機，希望大家多多包涵。如果想看詳細一點的題解，

連結： http://blog.csdn.net/lyd_7_29/article/details/51637686

Code

var a,f,d:array[] of int64;
    i,j,l,r,n:longint;
function min(a,b:int64):int64;
begin
    if a<b then exit(a) else exit(b);
end;
function jj(n:int64):int64;
begin
    exit(n*(n+) div );
end;
function xl(j,k:int64):real;
begin
    exit((*f[j]-*f[k]+sqr(j)-sqr(k)-j+k)/(*(j-k)));
end;
begin
    readln(n);
    for i:= to n do read(a[i]);
    f[n]:=a[n];
    d[]:=n;
    l:=;
    r:=;
    for i:=n- downto  do
    begin
        while (l<r)and(i<xl(d[l],d[l+])) do inc(l);
        f[i]:=f[d[l]]+a[i]+jj(d[l]-i-);
        while (l<r)and(xl(d[r],i)>xl(d[r-],d[r])) do dec(r);
        inc(r);
        d[r]:=i;
    end;
    writeln(f[]);
end.
           

——2016.6.12