[TIOJ] 1639. 尋找蘿莉第二彈

題目連結:http://tioj.infor.org/problems/1639

---

本題是校隊題，那時我根本不知道題目在幹嘛，後來被雷(解析)了後才知道原來是個裸最佳二元樹，不過要套四邊形不等式優化，但我根本不知道最佳二元樹的$O(N^3)$作法該怎麼做ww，想了很久加被雷後才知道，因為給定一棵最佳二元樹，其左右子樹也皆為最佳二元樹，所以可以列出$dp[l][r] = \displaystyle\min_{\forall l \leq k \leq r}(dp[l][k]+dp[k][r])+sum[l][r], $的轉移式，這時就可以$O(N^3)$的拿到大部分測資，不過最後那組要套2D/1D四邊形優化，簡述一下：對於一條轉移式$dp[i][j] = \displaystyle\min_{\forall i \leq k \leq j}(dp[i][k]+dp[k][j])$，定義$K_{i,j}$為會使dp[i][j]最小的那個k，則$K_{i,j-1} \leq K_{i,j} \leq K_{i+1,j}$，但是要如何運用這神奇的性質呢?那顯然要讓你的j-i值由小到大出現，不過可以其實也可以偷懶，就是從第一維從後跑回來，第二維再負責維持使j-i由小到大就好。然後就照著做就好www這應該是最簡單的四邊形不等式優化了吧XD，仔細觀察: \[\cdots \leq \cdots \leq \cdots \\ K_{i-2,j-3} \leq K_{i-2,j-2} \leq K_{i-1,j-2} \\ K_{i-1,j-2} \leq K_{i-1,j-1} \leq K_{i,j-1} \\ K_{i,j-1} \leq K_{i,j} \leq K_{i+1,j} \\ K_{i,j+1} \leq K_{i+1,j+1} \leq K_{i+2,j+1} \\ K_{i+2,j+1} \leq K_{i+2,j+2} \leq K_{i+3,j+2} \\ \cdots \leq \cdots \leq \cdots \] 你會發現每個元素都只會出現兩遍，也就是說總轉移最多O(2N)，所以在轉移時的複雜度就變成均攤$O(1)$了!!

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define N 4000

lld arr[N+5], sum[N+5];
lld dp[N+5][N+5];
int K[N+5][N+5];

lld f(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=0;i<n;i++)cin>>arr[i];
	sum[0]=arr[0];
	for(int i=1;i<n;i++)sum[i]=sum[i-1]+arr[i];
	for(int i=n-1;i>=0;i--){
		for(int j=i+1;j<=n;j++){
			if(j-i==1){
				dp[i][j]=0;
				K[i][j]=i;
			}else{
				dp[i][j]=9223372036854775807;
				for(int k=K[i][j-1];k<=K[i+1][j];k++){
					if(dp[i][k]+dp[k][j] < dp[i][j]){
						K[i][j]=k;
						dp[i][j]=dp[i][k]+dp[k][j];
					}
				}
				if(i==0)dp[i][j]+=sum[j-1];
				else dp[i][j]+=sum[j-1]-sum[i-1];
			}
		}
	}
	cout<<dp[0][n];
	return 0;
}