[TIOJ] 1745. [APIO '10] Commando
題目連結: http://tioj.infor.org/problems/1745 這題應該不難想到DP的方式\[ f(x) =ax^2+bx+c \\ dp[i] = \max_{0 \leq j #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();...