Mỗi \(j\) là một đường thẳng \(y = m_j \cdot x + b_j\). Tập các đường thẳng này tạo thành bao lồi dưới (lower convex hull). Khi \(x\) tăng dần (tức \(S[i]\) tăng), đường thẳng tối ưu cũng dịch chuyển về bên phải → ta có thể dùng deque thay vì tìm kiếm nhị phân.
graph LR
A["j=0: y = 0x + 0"] --> B["j=1: y = -6x + 9"]
B --> C["j=2: y = -8x + 16"]
C --> D["j=3: y = -16x + 64"]
Tại \(x = 3\): đường \(j=1\) (\(y=-9\)) tốt hơn \(j=0\) (\(y=0\)).
Tại \(x = 8\): đường \(j=3\) (\(y=-64\)) tốt nhất.
Nếu cần \(\max\) thay vì \(\min\):
- Đường thẳng phải tạo thành bao lồi trên (upper convex hull)
- Dấu bất đẳng thức trong hàm bad bị đảo ngược
- Hệ số góc \(m\) phải giảm dần (thay vì tăng dần)
Nếu \(m\) không tăng/giảm đều → không thể pop từ deque:
- Cách 1: Dùng Li Chao Tree (\(O(\log X)\) mỗi truy vấn)
- Cách 2: Dùng Dynamic CHT với tìm kiếm nhị phân trên deque
Nếu \(S[i]\) không tăng dần → không thể pop_front:
- Cách: Dùng tìm kiếm nhị phân trên deque thay vì pop_front (CHT query\(O(\log N)\))
- Hoặc dùng Li Chao Tree
Trong CHT, phép nhân chéo ((b.b - a.b) * (a.m - c.m)) có thể vượt quá long long:
- Dùng __int128 trong C++ hoặc Decimal trong Python
- Trong Python, số nguyên không giới hạn nên ít gặp vấn đề hơn
#include<bits/stdc++.h>usingnamespacestd;// Cấu trúc biểu diễn đường thẳng y = m*x + bstructLine{longlongm,b;// hệ số góc m, tung độ gốc blonglongeval(longlongx){returnm*x+b;}// tính giá trị y tại x};structCHT{deque<Line>lines;// tập đường thẳng, lưu trong deque// Kiểm tra: đường c có làm đường b "vô dụng" không?// a, b, c theo thứ tự thêm vào. Trả về true nếu giao(a,b) >= giao(a,c)boolbad(Linea,Lineb,Linec){// Dùng __int128 để tránh tràn số khi nhân// giao(a,b) = (b.b - a.b) / (a.m - b.m)// So sánh: giao(a,b) >= giao(a,c) → b bị c "che"return(__int128)(b.b-a.b)*(a.m-c.m)>=(__int128)(c.b-a.b)*(a.m-b.m);}// Thêm đường thẳng mới với hệ số góc m và tung độ gốc bvoidadd(longlongm,longlongb){Linel={m,b};// Xóa các đường thẳng bị đường mới "che" — giữ bao lồi dướiwhile(lines.size()>=2&&bad(lines[lines.size()-2],lines[lines.size()-1],l))lines.pop_back();// đường giữa bị vô hiệu → xóalines.push_back(l);// thêm đường mới vào cuối}// Truy vấn giá trị nhỏ nhất tại x (x đơn điệu tăng)longlongquery(longlongx){// Xóa các đường ở đầu deque nếu chúng không còn tối ưuwhile(lines.size()>=2&&lines[0].eval(x)>=lines[1].eval(x))lines.pop_front();// đường đầu không còn tốt nhất → xóareturnlines[0].eval(x);// trả về giá trị của đường tối ưu}};intmain(){intn;cin>>n;// Nhập dãy a và tính mảng cộng dồn svector<longlong>a(n+1),s(n+1,0);for(inti=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];// s[i] = a[1] + ... + a[i]}// dp[i] = min(dp[j] + (s[i] - s[j])^2)// = s[i]^2 + min(dp[j] + s[j]^2 - 2*s[j]*s[i])// Đặt m = -2*s[j], b = dp[j] + s[j]^2, x = s[i]// → dp[i] = x^2 + min_j(m * x + b)vector<longlong>dp(n+1,LLONG_MAX);dp[0]=0;// chi phí 0 phần tử = 0CHTcht;cht.add(0,0);// j=0: m=-2*0=0, b=dp[0]+0^2=0for(inti=1;i<=n;i++){dp[i]=s[i]*s[i]+cht.query(s[i]);// s[i]^2 + min(m*s[i]+b)cht.add(-2*s[i],dp[i]+s[i]*s[i]);// thêm đường thẳng cho j=i}cout<<dp[n]<<"\n";// kết quả: chi phí nhỏ nhất cho N phần tửreturn0;}
fromcollectionsimportdequeimportsysinput=sys.stdin.readlinen=int(input())# Nhập dãy a, thêm 0 ở đầu để đánh chỉ số từ 1a=[0]+list(map(int,input().split()))# Mảng cộng dồn s: s[i] = a[1] + ... + a[i]s=[0]*(n+1)foriinrange(1,n+1):s[i]=s[i-1]+a[i]classCHT:def__init__(self):self.lines=deque()# tập đường thẳng, lưu trong deque# Kiểm tra: đường c có làm đường b "vô dụng" không?def_bad(self,a,b,c):# So sánh giao điểm: giao(a,b) >= giao(a,c) → b bị c "che"return(b[1]-a[1])*(a[0]-c[0])>=(c[1]-a[1])*(a[0]-b[0])defadd(self,m,b):l=(m,b)# mỗi đường thẳng là tuple (m, b)# Xóa các đường bị đường mới "che"whilelen(self.lines)>=2andself._bad(self.lines[-2],self.lines[-1],l):self.lines.pop()# đường giữa vô dụng → xóaself.lines.append(l)# thêm đường mớidefquery(self,x):# Xóa các đường đầu nếu không còn tối ưu tại xwhilelen(self.lines)>=2and \
self.lines[0][0]*x+self.lines[0][1]>=self.lines[1][0]*x+self.lines[1][1]:self.lines.popleft()# đường đầu tệ hơn đường thứ 2 → xóareturnself.lines[0][0]*x+self.lines[0][1]# giá trị đường tối ưu# dp[i] = chi phí nhỏ nhất cho i phần tử đầu tiêndp=[float('inf')]*(n+1)dp[0]=0# chi phí 0 phần tử = 0cht=CHT()cht.add(0,0)# j=0: m=0, b=0foriinrange(1,n+1):# dp[i] = s[i]^2 + min_{j<i}( -2*s[j]*s[i] + dp[j] + s[j]^2 )dp[i]=s[i]*s[i]+cht.query(s[i])cht.add(-2*s[i],dp[i]+s[i]*s[i])# thêm đường thẳng cho j=iprint(dp[n])# kết quả cuối cùng
Li Chao Tree — Dùng khi \(m\) và \(x\) không đơn điệu¶
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;// Mỗi đường thẳng: y = m*x + bstructLine{llm,b;lleval(llx){returnm*x+b;}};structLiChao{staticconstllMAX_X=1e9;// phạm vi x cần truy vấnstructNode{Lineline={0,LLONG_MAX};// mặc định: đường "vô cực"Node*l=nullptr,*r=nullptr;// con trái, con phải};Node*root=newNode();// nút gốc// Thêm đường thẳng line vào nút u quản lý đoạn [lo, hi]voidinsert(Node*&u,lllo,llhi,Lineline){if(!u)u=newNode();llmid=(lo+hi)/2;// Nếu đường mới tốt hơn tại mid → đổi chỗboolleft=line.eval(lo)<u->line.eval(lo);boolm_better=line.eval(mid)<u->line.eval(mid);if(m_better)swap(u->line,line);// giữ đường tốt nhất ở nútif(lo==hi)return;// đoạn 1 điểm → dừng// Đệ quy sang 1 trong 2 conif(left!=m_better)insert(u->l,lo,mid,line);// đường mới tốt hơn bên tráielseinsert(u->r,mid+1,hi,line);// hoặc tốt hơn bên phải}// Truy vấn giá trị nhỏ nhất tại xllquery(Node*u,lllo,llhi,llx){if(!u)returnLLONG_MAX;llres=u->line.eval(x);// giá trị đường ở nút hiện tạillmid=(lo+hi)/2;if(x<=mid)res=min(res,query(u->l,lo,mid,x));// tìm tiếp bên tráielseres=min(res,query(u->r,mid+1,hi,x));// tìm tiếp bên phảireturnres;}// Wrapper tiện lợivoidadd(llm,llb){insert(root,-MAX_X,MAX_X,{m,b});}llget(llx){returnquery(root,-MAX_X,MAX_X,x);}};intmain(){intn;cin>>n;vector<ll>a(n+1),s(n+1,0);for(inti=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];// mảng cộng dồn}vector<ll>dp(n+1,LLONG_MAX);dp[0]=0;LiChaolc;lc.add(0,0);// j=0for(inti=1;i<=n;i++){dp[i]=s[i]*s[i]+lc.get(s[i]);// truy vấn Li Chao Treelc.add(-2*s[i],dp[i]+s[i]*s[i]);// thêm đường thẳng mới}cout<<dp[n]<<"\n";return0;}
importsysinput=sys.stdin.readlinen=int(input())a=[0]+list(map(int,input().split()))s=[0]*(n+1)foriinrange(1,n+1):s[i]=s[i-1]+a[i]MAX_X=10**9# phạm vi xclassLiChao:classNode:__slots__=('m','b','l','r')# tiết kiệm bộ nhớdef__init__(self):self.m=0self.b=float('inf')# đường mặc định: vô cựcself.l=None# con tráiself.r=None# con phảidef__init__(self):self.root=self.Node()# Thêm đường thẳng y = m*x + b vào câydefadd(self,m,b):self._insert(self.root,-MAX_X,MAX_X,m,b)def_insert(self,u,lo,hi,m,b):mid=(lo+hi)//2# Nếu đường mới tốt hơn tại mid → đổi chỗdefev(m,b,x):returnm*x+bleft_better=ev(m,b,lo)<ev(u.m,u.b,lo)# tốt hơn bên trái?mid_better=ev(m,b,mid)<ev(u.m,u.b,mid)# tốt hơn ở mid?ifmid_better:u.m,m=m,u.m# đổi chỗ: giữ tốt nhất ở uu.b,b=b,u.biflo==hi:return# đoạn 1 điểm → dừngifleft_better!=mid_better:# chéo → đệ quy tráiifnotu.l:u.l=self.Node()self._insert(u.l,lo,mid,m,b)else:# cùng phía → đệ quy phảiifnotu.r:u.r=self.Node()self._insert(u.r,mid+1,hi,m,b)# Truy vấn giá trị nhỏ nhất tại xdefget(self,x):returnself._query(self.root,-MAX_X,MAX_X,x)def_query(self,u,lo,hi,x):ifnotu:returnfloat('inf')res=u.m*x+u.b# giá trị đường ở nút hiện tạimid=(lo+hi)//2ifx<=mid:res=min(res,self._query(u.l,lo,mid,x))else:res=min(res,self._query(u.r,mid+1,hi,x))returnresdp=[float('inf')]*(n+1)dp[0]=0lc=LiChao()lc.add(0,0)# j=0foriinrange(1,n+1):dp[i]=s[i]*s[i]+lc.get(s[i])lc.add(-2*s[i],dp[i]+s[i]*s[i])print(dp[n])