参考 肖然的博客
四边形不等式
原形式
有一个双变量函数 $f(x,y)$，如果对于 $\forall a\le b\le c\le d$，都满足 $f(a,d)+f(b,c)\ge f(a,c)+f(b,d)$ 则称其满足 四边形不等式。
等价形式
对于 $\forall a<b$，都有 $f(a,b+1)+f(a+1,b)\ge f(a,b)+f(a+1,b+1)$。
这一形式的必要性显然，下证其充分性：
若 $a+1<b$ 则：
\[\begin{aligned} f(a,b+1)+f(a+1,b)&\ge f(a,b)+f(a+1,b+1)\cr f(a+1,b+1)+f(a+2,b)&\ge f(a+1,b)+f(a+2,b+1) \end{aligned}\]两式相加，得
\[f(a,b+1)+f(a+2,b)\ge f(a,b)+f(a+2,b+1)\]原来的 a+1 可以扩展到 a+2，用类似方法，可扩展成：
\[\forall a^{\prime}>a,f(a,b+1)+f(a^{\prime},b)\ge f(a,b)+f(a^{\prime},b+1)\]b 的扩展方式类似，就是把原式带入 $b^{\prime}=b-1$ 然后相加即可。
1D1D
\[dp(i)=\min_{j<i}(dp(j)+w(j,i))\]其中 w 函数满足四边形不等式时，转移具有 决策单调性，每次的决策点都在上次的后头，下证之：
单调性证明
设第 i 项的决策点为 $p(i)$，则对 $\forall j<i$：
\[\begin{aligned} dp(p(i))+w(p(i),i)&\le dp(j)+w(j,i)\cr w(p(i),i+1)+w(j,i)&\le w(p(i),i)+w(j,i+1) \end{aligned}\]两式相加，得：
\[dp(p(i))+w(p(i),i+1)\le dp(j)+w(j,i+1)\]所以 $p(i+1)\ge p(i)$。
P3515 [POI2011]Lightning Conductor
老师的代码交到黑暗爆炸 OJ 被卡了
把原式移项，得 $p=\max(a_j-a_i+\sqrt{|i-j|)}$，发现满足决策单调性，只需正着搞一遍，反着搞一遍即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
const int MXN=5e5+5;
int n,arr[MXN];
double p1[MXN],p2[MXN];
template<class T1,class T2>
struct pr{
T1 fi;T2 se;
inline pr(T1 fi=0,T2 se=0):fi(fi),se(se){}
};
pr<int,int> q[MXN];int ql,qr;
inline double f(int i,int j){return sqrt(i-j)+arr[j]-arr[i];}
inline void solve(double *p){
ql=1,qr=0;
for(int i=1;i<=n;i++){
while(ql<=qr && f(max(q[qr].se,i),i)>=f(max(q[qr].se,i),q[qr].fi))qr--;
if(ql>qr)q[++qr]=pr<int,int>(i,1);
else{
int l=max(i,q[qr].fi),r=n+1;
while(l<r){
int mid=(l+r)>>1;
f(mid,i)>=f(mid,q[qr].fi)?r=mid:l=mid+1;
}
q[++qr]=pr<int,int>(i,l);
}
while(ql<qr && q[ql+1].se<=i)ql++;
p[i]=f(i,q[ql].fi);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",arr+i);
solve(p1);
reverse(arr+1,arr+1+n);
solve(p2);
for(int i=1;i<=n;i++)
printf("%d\n",(int)ceil(max(p1[i],p2[n-i+1])));
return 0;
}
P1912 [NOI2009] 诗人小G
依然有决策单调性，推导甚是麻烦，略。这个答案超过 1e18 不太好搞，不妨用 long double 存答案，最后再判。
代码：（加了快读就是最优解）
#include<bits/stdc++.h>
using namespace std;
template<class T1,class T2>struct pr{T1 x;T2 y;};
template<class T1,class T2>inline pr<T1,T2> mp(T1 x,T2 y){return pr<T1,T2>{x,y};}
typedef long long ll;
typedef long double ld;
const int MXN=1e5+5;
const int MXS=35;
int t,n,stdlen,p,len[MXN];
char str[MXN][MXS];
inline ld qpow(ld x,int y){
ld r=1;
while(y){
if(y&1)r*=x;
x*=x,y>>=1;
}
return r;
}
#define w(x,y) (dp[x]+qpow(abs(len[y]-len[x]-stdlen),p))
int ql,qr,tran[MXN];
pr<int,int> q[MXN];
ld dp[MXN];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&stdlen,&p);stdlen++;
q[qr=ql=1]=mp(0,1);
for(int i=1;i<=n;i++){
str[i][0]=0;
scanf("%s",str[i]+1);
len[i]=strlen(str[i]+1)+len[i-1]+1;
}
for(int i=1;i<=n;i++){
while(ql<qr && q[ql+1].y<=i)ql++;
tran[i]=q[ql].x;
dp[i]=w(tran[i],i);
while(ql<=qr && w(i,q[qr].y)<w(q[qr].x,q[qr].y))qr--;
if(ql>qr)q[++qr]=mp(i,i);
else{
int l=q[qr].y,r=n+1,mid;
while(l<r){
mid=(l+r)>>1;
if(w(i,mid)<w(q[qr].x,mid))r=mid;
else l=mid+1;
}
if(l<=n)q[++qr]=mp(i,l);
}
}
if(dp[n]>1e18)printf("Too hard to arrange\n");
else{
printf("%lld\n",(ll)dp[n]);
for(int i=n;i;i=tran[i])str[i][0]=-1;
for(int i=1;i<=n;i++){
printf("%s",str[i]+1);
putchar(str[i][0]?'\n':' ');
}
}
puts("--------------------");
}
return 0;
}
2D1D
对于形式如下的 dp 转移：
\[\begin{aligned} dp(i,j)=&\min_{k\in[i,j)}(dp(i,k)+dp(k+1,j))+w(i,j)\cr dp(i,j)=&\min_{k\in[i,j)}(dp(i-1,k)+w(k+1,j))\cr \end{aligned}\]且：
- 函数 w 满足四边形不等式
- $\forall a\le b\le c\le d, w(a,d) \ge w(b,c)$
可以证明 $p(i,j-1) \le p(i,j) \le p(i+1,j)$，k 只需在这个范围内枚举，复杂度变为 $O(n^2)$，不会证，详见 OI-wiki。 实际运用中打个表就知道满不满足决策单调性了。
AcWing 282. 石子合并
转移：
\[dp(i,j)=\min_{k\in[i,j)}(dp(i,k)+dp(k+1,j))+\underbrace{s[j]-s[i-1]}_{w(i,j)};\]$w(i,j)$ 满足条件，所以有决策单调性。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MXN=305;
int n,arr[MXN],dp[MXN][MXN],t[MXN][MXN];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",arr+i);
t[i][i]=i;
arr[i]+=arr[i-1];
}
for(int i=n;i;i--)
for(int j=i+1;j<=n;j++){
dp[i][j]=1e9;
for(int k=t[i][j-1];k<=t[i+1][j];k++)
if(dp[i][j]>dp[i][k]+dp[k+1][j]){
dp[i][j]=dp[i][k]+dp[k+1][j];
t[i][j]=k;
}
dp[i][j]+=arr[j]-arr[i-1];
}
/*for(int i=1;i<=n;i++,putchar('\n'))
for(int j=1;j<=n;j++)
printf("%3d",t[i][j]);*/
printf("%d",dp[1][n]);
return 0;
}
AcWing 336. 邮局
山区建小学，每个区间都建在中位数上，依然有决策单调性。
代码：
#include<bits/stdc++.h>
using namespace std;
const int MXP=35;
const int MXN=305;
int n,p,x[MXN],sx[MXN];
int dp[MXP][MXN],t[MXP][MXN];
inline int w(int l,int r){
int mid=(l+r)>>1;
return sx[r]+sx[l-1]-(sx[mid]<<1)+x[mid]*((mid<<1)-l-r+1);
}
int main(){
scanf("%d%d",&n,&p);
for(int i=1;i<=n;i++){
scanf("%d",x+i);
sx[i]=sx[i-1]+x[i];
if(i<=p)t[i+1][i]=i-1;
}
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int j=1;j<=n;j++){
t[p+1][j]=j-1;
for(int i=min(j,p);i;i--)
for(int k=t[i][j-1];k<=t[i+1][j];k++){
if(dp[i][j]>dp[i-1][k]+w(k+1,j)){
dp[i][j]=dp[i-1][k]+w(k+1,j);
t[i][j]=k;
}
}
}
/*
for(int i=1;i<=p+1;i++,putchar('\n'))
for(int j=1;j<=n;j++)
cerr<<t[i][j]<<" ";
*/
printf("%d",dp[p][n]);
return 0;
}
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: