Quadrilateral inequality optimization represents a powerful technique for optimizing certain types of dynamic programming solutions, particularly thoce involving 2D1D state transitions.
The fundamental form of such DP equations is:
[f_{l,r}=\min_{k=l}^{r-1}{f_{l,k}+f_{k+1,r}}+w(l,r) ]
When the function w(l,r) satisfies specific properties, we can leverage decision monotonicity to optimize the solution.
- Interval Inclusion Monotonicity: For all l ≤ l' ≤ r' ≤ r, w(l',r') ≤ w(l,r), indicating w is monotonic with respect to interval inclusion.
- Quadrilateral Inequality: For all l₁ ≤ l₂ ≤ r₁ ≤ r₂, w(l₁,r₁) + w(l₂,r₂) ≤ w(l₁,r₂) + w(l₂,r₁) (cross is less than containment), then w satisfies the quadrilateral inequality. When equality always holds, w satisfies the quadrilateral identity.
- If for all integers a < b in the domain, w(a,b+1) + w(a+1,b) ≥ w(a,b) + w(a+1,b+1), then w satisfies the quadrilateral inequality.
For a < c, we have w(a,c+1) + w(a+1,c) ≥ w(a,c) + w(a+1,c+1)
For a+1 < c, we have w(a+1,c+1) + w(a+2,c) ≥ w(a+1,c) + w(a+2,c+1)
Adding these gives w(a,c+1) + w(a+2,c) ≥ w(a,c) + w(a+2,c+1)
That is, for any a ≤ b ≤ c, w(a,c+1) + w(b,c) ≥ w(a,c) + w(b,c+1).
Similarly, for any a ≤ b ≤ c ≤ d, w(a,d) + w(b,c) ≥ w(a,c) + w(b,d).
- If w(l,r) satisfies both interval inclusion monotonicity and quadrilateral inequality, then f(l,r) satisfies the quadrilateral inequality.
- If the state f satisfies the quadrilateral inequality, let m_{l,r} = min{k: f_{l,r} = g_{k,l,r}} be the optimal decision point, then:
[m_{l,r-1}\le m_{l,r}\le m_{l+1,r} \space (l+1 u, then u+1 ≤ k₁+1 ≤ r-1 ≤ r, and:
[f_{u+1,r-1}+f_{k_1+1,r}\le f_{u+1,r}+f_{k_1+1,r-1} ]
Since u is the optimal decision point for f_{l,r}:
[f_{l,u}+f_{u+1,r}\le f_{l,k_1}+f_{k_1+1,r} ]
Adding these equations gives:
[f_{l,u}+f_{u+1,r-1}\le f_{l,k_1}+f_{k_1+1,r-1} ]
That is, g_{u,l,r-1} ≤ g_{k₁,l,r-1}, so u = m_{l,r-1}, contradicting k₁ > u.
Therefore, k₁ ≤ u.
- If u > k₂, then l ≤ l+1 ≤ k₂ ≤ u, and:
[f_{l,k_2}+f_{l+1,u}\le f_{l,u}+f_{l+1,k_2} ]
Since k₂ is the optimal decision point for f_{l+1,r}:
[f_{l+1,k_2}+f_{k_2+1,r}\le f_{l+1,u}+f_{u+1,r} ]
Adding these equations gives:
[f_{l,k_2}+f_{k_2+1,r}\le f_{l,u}+f_{u+1,r} ]
That is, g_{k₂,l,r} ≤ g_{u,l,r}, so k₂ = m_{l,r}, contradicting u > k₂.
Therefore, u ≤ k₂.
Thus, k₁ ≤ u ≤ k₂, meaning m_{l,r-1} ≤ m_{l,r} ≤ m_{l+1,r}.
With decision monotonicity established, we can optimize the DP as follows:
When calculating f_{l,r}, record its optimal decision point m_{l,r}. The total enumeration of decision points is:
[\sum_{1\le l\le r\le n}m_{l+1,r}-m_{l,r-1}=\sum_{i=1}^{n}m_{i,n}-m_{1,i}\le n^2 ]
The implementation looks like this:
for(int len=2;len<=n;len++)
for(int l=1,r=len;r<=n;l++,r++){
f[l][r]=inf;
for(int k=m[l][r-1];k<=m[l+1][r];k++)
if(f[l][r]>f[l][k]+f[k+1][r]+w(l,r)){
f[l][r]=f[l][k]+f[k+1][r]+w(l,r);
m[l][r]=k;
}
}
P4767 [IOI2000] Post Office
Given n points {a} on a number line, place m points to minimize:
[\sum_{i=1}^{n}\min_{j=1}^{m}|a_i-b_j| ]
where n ≤ 3000, m ≤ 300.
First, sort a in ascending order.
Let f(i,j) represent the minimum value considering the first i points with j placed points.
Then:
[f(i,j)=\min_{k=0}^{i-1}f(k,j-1)+w(k+1,i) ]
where w(l,r) is the minimum distance sum for placing one point in this interval.
Clearly, this point should be at the median of the interval, which can be computed directly.
The complexity is O(n³m).
Considering whether we can achieve O(1) per transition, we find that w can be preprocessed in O(n²) time:
[w(l,r)=w(l,r-1)+a_r-a_{\lfloor\frac{l+r}{2}\rfloor} ]
But the complexity remains O(n²m).
Let's examine if w satisfies the quadrilateral inequality.
From the recurrence:
[w(l,r+1)-w(l,r)=a_{r+1}-a_{\lfloor\frac{l+r+1}{2}\rfloor} ] [w(l+1,r+1)-w(l+1,r)=a_{r+1}-a_{\lfloor\frac{l+r+2}{2}\rfloor} ]
Subtracting these gives:
[w(l,r+1)+w(l+1,r)-w(l,r)-w(l+1,r+1)=a_{\lfloor\frac{l+r+1}{2}\rfloor}-a_{\lfloor\frac{l+r+2}{2}\rfloor} ]
Since coordinates are increasing, the above expression ≤ 0.
Therefore:
[w(l,r)+w(l+1,r+1)\le w(l,r+1)+w(l+1,r) ]
Thus f satisfies the quadrilateral inequality, allowing us to use decision monotonicity for optimization.
Time complexity: O(nm).
#include<bits/stdc++.h>
#define N 3010
#define M 305
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,m,a[N];
int w[N][N],f[N][M],b[N][M];
void init(){
for(int l=1;l<=n;l++){
w[l][l]=0;
for(int r=l+1;r<=n;r++)
w[l][r]=w[l][r-1]+a[r]-a[(l+r)>>1];
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
sort(a+1,a+1+n);
memset(f,0x3f,sizeof(f));
init(),f[0][0]=0;
for(int j=1;j<=m;j++){
b[n+1][j]=n;
for(int i=n;i;i--){
for(int k=b[i][j-1];k<=b[i+1][j];k++)
if(f[i][j]>f[k][j-1]+w[k+1][i])
f[i][j]=f[k][j-1]+w[k+1][i],b[i][j]=k;
}
}
printf("%d\n",f[n][m]);
return 0;
}
P3515 [POI2011] Lightning Conductor
Given sequence {a_n}, for each i ∈ [1,n], find the smallest non-negative integer p such that ∀j ∈ [1,n], a_j ≤ a_i + p - √|i-j|.
n ≤ 5×10⁵, 0 ≤ a_i ≤ 10⁹.
[p\ge a_j+\sqrt{|i-j|}-a_i ] [p=\lceil\max{a_j+\sqrt{|i-j|}}\rceil-a_i ]
Process once forward, then reverse the sequence and process again to eliminate the absolute value.
Let f(i) = max{a_j + √(i-j)}, w(j,i) = √(i-j).
For l+1 < r:
[w(l,r+1)+w(l+1,r)-w(l,r)-w(l+1,r+1) ] [=\sqrt{r-l-1}+\sqrt{r-l+1}-2\sqrt{r-l} ]
Let t = r-l:
[=(\sqrt{t+1}-\sqrt{t})-(\sqrt{t}-\sqrt{t-1}) ]
This expression is < 0.
Then for all a ≤ b ≤ c ≤ d, w(a,d) + w(b,c) ≤ w(a,c) + w(b,d).
This problem involves finding max, so by taking the negative sign, we can prove f has decision monotonicity.
Define P_i as the optimal decision point for i.
For all j ∈ [0, P_i-1], we have:
[f(P_i)+w(P_i,i)\le f(j)+w(j,i) ]
Since w satisfies the quadrilateral inequality, for all i' ∈ [i+1,n], we have:
[w(j,i')+w(P_i,i)\ge w(j,i)+w(P_i,i') ] [w(P_i,i')-w(P_i,i)\le w(j,i')-w(j,i) ]
Adding to the first inequality:
[f(P_i)+w(P_i,i')\le f(j)+w(j,i') ]
That is, the optimal decision point for i' must be ≥ P_i, so f has decision monotonicity.
To find f(i), we consider which f(i') it can be the optimal decision for.
Based on decision monotonicity, we can find a pos such that decisions before this are better than i, and those after are worse.
Change this position and everything after to i, so their optimal decision points are all i.
Establish a queue to replace P, storing triples (j,l,r), meaning P(l~r) are all j.
For each i, perform the following operations:
-
Let the queue head be (j₀,l₀,r₀). If r₀ = i-1, remove the head because f(i) values before have been computed, otherwise set l₀ = i.
-
Take the optimal decision j from the head to compute f(i).
-
Insert the new decision i:
(1) Take the queue tail (j_t,l_t,r_t).
(2) If for f(l_t), i is better than j_t, i.e., f(i)+w(i,l_t) ≤ f(j)+w(j_t,l_t), record pos = l_t, remove the tail and return to (1).
(3) If for f(r_t), i is better than j_t, go to (5).
(4) Otherwise, binary search pos in [l_t,r_t], where decisions before are better then i and those after are worse. Change [l_t,r_t] to [l_t,pos-1] and go to (5).
(5) Insert the triple (i,pos,n) at the queue tail.
Time complexity: O(n log n).
For this problem, simply take the negative sign.
#include<bits/stdc++.h>
#define db double
#define N 500010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,a[N],h,t;
db f[N],sqr[N];
struct node{
int l,r,p;
}q[N];
db w(int j,int i){
return db(a[j])+sqr[i-j];
}
int find(int t,int x){
if(calc(t,n)<calc(x,n))return n+1;
int pos=-1,l=x,r=q[t].r,mid;
while(l<=r){
mid=(l+r)>>1;
if(w(q[t].p,mid)<=w(x,mid))pos=mid,r=mid-1;
else l=mid+1;
}
return pos;
}
void insert(int i){
q[t].l=max(q[t].l,i);
while(h<=t&&w(i,q[t].l)>=w(q[t].p,q[t].l))t--;
if(h>t)q[++t]=(node){i,n,i};
else{
int pos=find(t,i);
if(pos>n)return;
q[t].r=pos-1;
q[++t]=(node){pos,n,i};
}
}
void work(){
h=1,t=0;
for(int i=1;i<=n;i++){
insert(i);
if(h<=t&&q[h].r<i)h++;
else q[h].l=i;
f[i]=max(f[i],w(q[h].p,i));
}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
sqr[i]=sqrt(i);
}
work();
for(int i=1;i<=n/2;i++)
swap(a[i],a[n-i+1]),swap(f[i],f[n-i+1]);
work();
for(int i=n;i;i--)
printf("%d\n",(int)ceil(f[i])-a[i]);
return 0;
}
P1912 [NOI2009] Poet Xiao G
Given n strings with lengths a_i, arrange them in order and divide into several segments. The cost of segment [l,r] is:
[\Big|(a_l+1+a_{l+1}+1+\dots+a_{r-1}+1+a_r)-L\Big|^P ]
Minimize the total cost and provide the solution. Multiple test cases.
- If the answer exceeds 10¹⁸, output "Too hard to arrange".
- Limit data: T ≤ 5, n ≤ 10⁵, L ≤ 3×10⁶, P ≤ 10.
- All a_i ≤ 30.
Let a_i+1, and s_x = Σ_{i=1}^{x} a_i.
The DP equation is:
[f_i=\min_{j=0}^{i-1}{f_j+|s_i-s_j-(L+1)|^P} ]
This is a high-degree polynomial, so slope optimization doesn't apply.
If we prove w(j,i) = |s_i-s_j-(L+1)|^P satisfies the quadrilateral inequality, we can solve it with a monotonic queue.
[\Rightarrow w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1) ]
Let:
[u=s_i-s_j-(L+1),v=s_i-s_j-a_j-(L+1) ] [|u+a_{i+1}|^P+|v|^P\ge|u|^P+|v+a_{i+1}|^P ] [\Rightarrow |v|^P-|v+a_{i+1}|^P\ge|u|^P-|u+a_{i+1}|^P ]
Since u ≥ v, we need to prove g(x) = |x|^P - |x+z|^P (z ∈ [0,+∞)) is non-strictly decreasing.
Breaking down the absolute values:
- x ∈ [0,∞): This is relatively obvious by inspection.
Taking derivatives:
[g'(x)=Px^{P-1}-P(x+z)^{P-1} ]
It's easy to see g'(x) < 0.
- x ∈ (-∞,0), P ≡ 0 (mod 2)
This becomes (-x)^P - (-x+z)^P, which is decreasing like above.
- x ∈ [-z,0), P ≡ 1 (mod 2)
[g(x)=-x^P-(x+z)^P ] [g'(x)=-Px^{P-1}-P(x+z)^{P-1} ]
Since P is odd, g'(x) ≤ 0.
- x ∈ (-∞,-z), P ≡ 1 (mod 2)
[g(x)=-x^P+(x+z)^P ] [g'(x)=-Px^{P-1}+P(x+z)^{P-1} ]
Similarly, g'(x) ≤ 0.
I'm not sure why such rigorous proof is needed.
Let's review the process again. I still don't quite understand.
Establish a queue to replace P, storing triples (j,l,r), meaning P(l~r) are all j.
For each i, perform the following operations:
-
Let the queue head be (j₀,l₀,r₀). If r₀ = i-1, remove the head because f(i) values before have been computed, otherwise set l₀ = i.
-
Take the optimal decision j from the head to compute f(i).
-
Insert the new decision i:
(1) Take the queue tail (j_t,l_t,r_t).
(2) If for f(l_t), i is better than j_t, i.e., f(i)+w(i,l_t) ≤ f(j)+w(j_t,l_t), record pos = l_t, remove the tail and return to (1).
(3) If for f(r_t), i is better than j_t, go to (5).
(4) Otherwise, binary search pos in [l_t,r_t], where decisions before are better then i and those after are worse. Change [l_t,r_t] to [l_t,pos-1] and go to (5).
(5) Insert the triple (i,pos,n) at the queue tail.
Time complexity: O(Tn log n).
When the answer exceeds 10¹⁸, long long will overflow, so we need to use long double to sacrifice precision for range.
#include<bits/stdc++.h>
#define ll long long
#define lb long double
#define N 100010
#define R 32
using namespace std;
char st[N][R];
int T,n;
ll L,P,s[N];lb f[N];
int h,t,q[N],pre[N];
int stk[N],top;
lb qpow(lb k,ll b){
lb ret=1;
while(b){
if(b&1)ret*=k;
b>>=1,k*=k;
}
return ret;
}
lb calc(int j,int i){
return f[j]+qpow(abs(s[i]-s[j]-L),P);
}
int find(int t,int x){
if(calc(t,n)<calc(x,n))return n+1;
int pos=-1,l=x,r=n,mid;
while(l<=r){
mid=(l+r)>>1;
if(calc(x,mid)<=calc(t,mid))pos=mid,r=mid-1;
else l=mid+1;
}
return pos;
}
void work(){
h=1,t=0,q[++t]=0;
for(int i=1;i<=n;i++){
while(h<t&&find(q[h],q[h+1])<=i)h++;
pre[i]=q[h],f[i]=calc(q[h],i);
while(h<t&&find(q[t-1],q[t])>=find(q[t],i))t--;
q[++t]=i;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%lld%lld",&n,&L,&P),L++;
for(int i=1;i<=n;i++){
scanf("%s",st[i]);
s[i]=s[i-1]+strlen(st[i])+1;
}
work();
if(f[n]>1e18){
printf("Too hard to arrange\n");
}
else{
printf("%lld\n",(ll)f[n]),top=0;
for(int tp=n;tp;tp=pre[tp])stk[++top]=tp;
stk[++top]=0;
for(int i=top;i>1;i--){
for(int j=stk[i]+1;j<stk[i-1];j++)
printf("%s ",st[j]);
printf("%s\n",st[stk[i-1]]);
}
}
printf("--------------------\n");
}
return 0;
}
Yet Another Minimization Problem
Divide sequence a into m segments, where the cost of each segment [l,r] is the number of pairs of identical elements, i.e., Σ_{l≤x