轉站通知

本站已停止更新!!想繼續收看我的新文章的話,請前往我的新Blog - Chino's

2015年2月28日 星期六

TIOJ::1676 . 烏龜疊疊樂

http://tioj.ck.tp.edu.tw/problems/1676
這題整整寫了快幾個月了啊....,從第一次看到到寫出來大概一年多了吧.....。
明明是簡單版(或說特殊版)的DP單調對列斜率優化的說。



題目是,有一個烏龜塔,這裡可能有稍微改一下題目敘述,因為我覺得原本的敘述真的有點會讓人誤解。
烏龜塔有一個數值,叫做違和度,違和度是由烏龜疊起來的。每隻烏龜都有自己的違和度Xi,每個在高度 m的烏龜會放出 Xi * (m-1)的違和度,加總就是這個塔的違和度,可是很不幸的,每隻體積是 Y 的烏龜會放出 Y^2 的光芒(每隻烏龜體積是1),違和度減掉光芒才是他真正的違和度。

現在你可以把一些烏龜融合起來(每隻烏龜只可以被融合一次),變成大烏龜之後的烏龜違和度和體積都加總,高度還是 1 ,放出的光芒也相對的變成了合起來後的體積的平方

求:在最多融合K隻烏龜的限制下,怎樣融合可以讓烏龜塔的違和度最大,求最大的違和度。

題目很複雜,讀懂後整理一下,假設一下DP狀態。設 SUM( i )為0~ i 的前綴和、DP(i)為第 i 層烏龜塔的違和度,我們要求的是 DP(n), n 是總層數。

DP[ i ] = (for j in  i-k to i-1) max( DP[j] + SUM( j ) - (i-j)^2 )

上面的 j 的邊界要注意0,其中加上前綴和比較難理解,因為每增加一層烏龜(不管底層烏龜多大隻),原本的違和度都只會增加 前綴和,因為第一層是乘以(1-1)=0,然後不管上面的烏龜怎麼融合,因為一隻只能背融合一次,等於總違和度還是前綴和,加上去剛剛好。

再來就是光芒了,因為現在是 i ,從 K 限制下找了一個 j ,i - j 就是這隻烏龜的體積,他的平方就是光芒強度。

這樣做是 N^2 會TLE,所以我們要利用斜率優化解決他。

首先利用國中教過的和的平方公式,把 i-j 的平方改成 i^2 - 2*i*j + j^2 ,然後我們發現 i 平方對於這次取MAX是定值,可以提出來,DP是變成:

DP[ i ] = (for j in  i-k to i-1) max( DP[j] + SUM( j ) -j*j +2*i*j ) - i*i 。

然後我們發現原本的DP式變成了一條一條的直線,y = a x + b,
a 是 2*j ,
b 是DP[j] + SUM( j ) -j*j
x 是這次的 i,
y - i*i 就是這次DP的值。

然後仔細看,他們的斜率遞增的!(因為 i 遞增)
所以這一堆直線,當後面的直線B帶入 i 值比現在的直線A大的話,後面的直線就永遠比現在的直線大了,我們可以稱為 A被 B 殺掉了。

現在我們維護一個單調對列 deque,每次在丟一調直線進去前,先檢查,是不是在 倒數第二條直線 T1 和倒數第一條直線 T2 、現在要加入的直線 T3 ,
T1被T2殺掉時,T2和T3誰比較大,
我們發現 T1和T2的交點X座標如果比T2和T3交點的X座標大,代表T2殺掉 T1時 早就被 T3先殺掉了,也就是T2根本沒有存在的價值,那就提前先把T2殺掉,維持單調對列裡面的交點X座標遞增,這樣每次只要依序檢察前兩條線帶入出來的值,如果後面殺掉前面就把前面給POP掉,就可以維持每次最前面那條線代出來的值是最大的。

到這裡都很正常,但是有一個我de了一年的bug,那就是,因為有限制K, T1可能會提早老死!!!!!!!

T1的壽命是在他入隊後 K 格之後,所以T1死掉的時間變成 和 T2的交點和 +K 取最小值,這個位置去和 T2 T3 交點X座標比較。

然後置於算座標除法誤差問題,這段是我的推測(有錯請留言告知),因為我們要求他們把對方殺掉的時間,如果兩個人都在兩個整數間把對發殺掉,那我們像下取整也只會讓他們等於,而就算這麼剛好好了,我們把他們都留下,在代數字的時候因為是整數所以真正大的也會浮出來,所以我們可以直接用 long long 除 long long

啊.......終於寫出來了.......。


#include <iostream>
#include <algorithm>
#include <queue>
#define F(n) Fi(i,n)
#define Fi(i,n) for(int i=0;i<n;i++)
#define N 500010
#define LL long long
using namespace std;
LL D[N],DP[N],n,k;
struct MP{
    LL a,b,i;
    MP(){}
    MP(LL _a,LL _b,LL _i):a(_a),b(_b),i(_i){}
};
bool tt(MP t1,MP t2,MP t3){
    return min(t1.i+k,(t2.b-t1.b)/(t1.a-t2.a)) > (t3.b-t2.b)/(t2.a-t3.a);
}
bool check(MP t1,MP t2,LL x){
    return t1.a*x+t1.b <= t2.a*x+t2.b;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=n;i>0;i--)cin>>D[i];
    F(n)D[i+1]+=D[i];
    deque<MP>qq;
    qq.push_back(MP(0,0,0));
    for(LL i=1;i<=n;i++){
        if(!qq.empty()&&qq.front().i<i-k)qq.pop_front();
        while(qq.size()>=2&&check(qq[0],qq[1],i))qq.pop_front();
        LL a=qq.front().a,b=qq.front().b;
        DP[i]=a*i+b-i*i;
        a=2*i,b=DP[i]+D[i]-i*i;
        while(qq.size()>=2&&tt(qq[qq.size()-2],qq[qq.size()-1],MP(a,b,i))){
            qq.pop_back();
        }
        qq.push_back(MP(a,b,i));
    }
    cout<<DP[n]<<endl;
    cin>>n;
}