Code 備忘錄►DP

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 - 2ij + j^2 ，然後我們發現 i 平方對於這次取MAX是定值，可以提出來，DP是變成：

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

然後我們發現原本的DP式變成了一條一條的直線，y = a x + b，
a 是 2j ，
b 是DP[j] + SUM( j ) -jj
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。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}