[TIOJ] 1745. [APIO '10] Commando

題目連結:http://tioj.infor.org/problems/1745
這題應該不難想到DP的方式\[ f(x) =ax^2+bx+c \\ dp[i] = \max_{0 \leq j < i}(f(\sum_{k=i+1}^{j}arr[k]) + dp[j]) \],但是也不難發現它的複雜度會是$O(n^2)$。這時就要優化他,可以發現它可以套用斜率優化,因為對轉移式做一些移項跟變數變換後會變成\[ S_i = \sum_{j=0}^{i} arr[j]\\ dp[i] = \max_{0 \leq j < i}(-2aS_j \cdot S_i + a{S_j}^2 - bS_j + dp[j]) + a{{S_i}^2} + bS_i + c \]那很明顯的可以發現若把j看成是定值,i看成是變數的話,就會發現max裡面那一坨就是一個一次函數,而且斜率會隨j增加而增加。然後我們會發現自己每次在轉移時都會比之前多一項j,所以其實可以看成每次轉移時加入一條線(或每次轉移後加入一條線),並且會發現當這條線(也就是這個j),已經有比他新的線比他好時,那他就不會被轉移到,此外,如果有些線在超越比他新的線前,已經被某條更新的線超越,則他也不會是可以拿來轉移的。有了這幾個性質,我們就可以發現要判斷有沒有新的線比他好,就等價於在一個deque中(裡面存著所有先前可以轉移的線),比較他的前兩個元素,如果第一項在帶入i時會比較小,那他就符合前面所說的第一種情況,可以被移除;第二種情況則是在將當前的線放入deque時,比較pos1(最末項跟當前項的交點)與pos2(最末項跟次末項的交點的x座標),如果pos1 < pos2,那最末的那條線就可以砍掉。發現每條線只會進deque一次,出一次,所以複雜度就壓到$O(n)$了
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define INF 2147483647
#define N 1000000

lld a,b,c;
lld arr[N+5], sm[N+5], dp[N+5];
inline bool detectBeyond(int,int,int);
inline lld f(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	cin>>a>>b>>c;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		sm[i]=arr[i]+sm[i-1];
	}
	for(int i=1;i<=n;i++)dp[i]=-INF;
	deque<int> dq;
	dq.push_back(0);
	for(int i=1;i<=n;i++){
		while(dq.size()>1 && f(dq[0], i) < f(dq[1], i)) dq.pop_front();
		dp[i] = f(dq[0], i) + a*sm[i]*sm[i]+b*sm[i]+c;
		while(dq.size()>1  && detectBeyond(dq[dq.size()-2], dq[dq.size()-1], i)) dq.pop_back();
		dq.push_back(i);
	}
	cout<<dp[n]<<'\n';
	return 0;
}
inline bool detectBeyond(int i, int j, int k){
	lld ai = -2*a*sm[i], bi=a*sm[i]*sm[i]-b*sm[i]+dp[i];
	lld aj = -2*a*sm[j], bj=a*sm[j]*sm[j]-b*sm[j]+dp[j];
	lld ak = -2*a*sm[k], bk=a*sm[k]*sm[k]-b*sm[k]+dp[k];
	return (bj-bi)*(aj-ak) >= (ai - aj)*(bk - bj);
}
inline lld f(int j,int i){
	return -2*a*sm[j]*sm[i]+a*sm[j]*sm[j]-b*sm[j]+dp[j];
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology