题解
简化一下题意，已知从 \((p,q)\) 直接到达 \((x,y)\) 的费用函数如下：
\[\text{cost}(p,q,x,y) = \begin{cases} w_p+w_q+w_x+w_y-p-q-x-y, & l1_x \le p \le r1_x,l2_y \le q \le r2_y \\ \text{inf}, & \text{otherwise} \\ \end{cases}\]问从 \((1,1)\) 到各位置的最小费用。
如果暴力建图跑最短路，由于 \(n\) 可以达到 \(\text{1e3}\)，一共有 \(n^2\) 个点，边更多，肯定爆炸。
不妨思考是否有 \(\text{DP}\) 的做法，如果设 \(dp_{i,j}\) 表示 \((1,1)\) 到 \((i,j)\) 的最小费用，则有：
\[dp_{x,y}=\min_{l1_x \le p \le r1_x,l2_y \le q \le r2_y}{(dp_{p,q}+\text{cost}(p,q,x,y))} \]注意到，\(r1_x<x\),\(r2_y<y\)，显然满足无后效性，可以 \(\text{DP}\)，但是暴力是 \(n^4\) 的，仍然超时。
将方程抽象成矩阵问题，有一个 \((n+1) \times (n+1)\) 的矩阵，因为有 0。每个位置 \((i,j)\) 有一个权值表示 \(dp_{i,j}+w_i+w_j-i-j\)。那么在求解 \((x,y)\) 时，相当于在一个子矩阵中求出最小权值 \(\text{Pre}\)，然后让 \(dp_{x,y}=\text{Pre}+w_x+w_y-x-y\)，接着修改 \((x,y)\) 处的数值为 \(dp_{x,y}+w_x+w_y-x-y\)。
也就是要维护子矩阵极值，单点修改。我们可以用 \(1\) 个线段树维护行，线段树的每个结点上维护一个线段树来维护列。即线段树套线段树，容易证明，单次操作是 \(O(\log^2 n)\) 的。总体的时间复杂度就是 \(O(n^2\log^2 n)\) 可以接受。
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int inf=1e9;
int n,l1[N],r1[N],l2[N],r2[N],w[N];
int dp[N][N],Pre;
struct node_y {
int l,r,val;
};
struct tree_y {
node_y tr[N<<2];
void pushup(int p) {
tr[p].val=min(tr[p<<1].val,tr[p<<1|1].val);
}
void build(int p,int l,int r) {
tr[p].l=l,tr[p].r=r;
if(l==r) {
tr[p].val=inf;
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void update(int p,int y,int k) {
if(tr[p].l==tr[p].r) {
tr[p].val=min(tr[p].val,k);
return;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(y<=mid) update(p<<1,y,k);
else update(p<<1|1,y,k);
pushup(p);
}
int query(int p,int l,int r) {
if(l<=tr[p].l&&tr[p].r<=r) return tr[p].val;
int mid=(tr[p].l+tr[p].r)>>1;
int val=inf;
if(l<=mid) val=min(val,query(p<<1,l,r));
if(r>mid) val=min(val,query(p<<1|1,l,r));
return val;
}
};
struct node_x {
int l,r;
tree_y T;
};
struct tree_x {
node_x tr[N<<2];
void build(int p,int l,int r) {
tr[p].l=l,tr[p].r=r;
tr[p].T.build(1,1,n+1);
if(tr[p].l==tr[p].r) return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void update(int p,int x,int y,int k) {
tr[p].T.update(1,y,k);
if(tr[p].l==tr[p].r) return;
int mid=(tr[p].l+tr[p].r)>>1;
if(x<=mid) update(p<<1,x,y,k);
else update(p<<1|1,x,y,k);
}
int query(int p,int lx,int rx,int ly,int ry) {
if(lx<=tr[p].l&&tr[p].r<=rx) return tr[p].T.query(1,ly,ry);
int mid=(tr[p].l+tr[p].r)>>1;
int val=inf;
if(lx<=mid) val=min(val,query(p<<1,lx,rx,ly,ry));
if(rx>mid) val=min(val,query(p<<1|1,lx,rx,ly,ry));
return val;
}
};
tree_x A;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>l1[i];
for(int i=1;i<=n;i++) cin>>r1[i];
for(int i=1;i<=n;i++) cin>>l2[i];
for(int i=1;i<=n;i++) cin>>r2[i];
for(int i=1;i<=n;i++) cin>>w[i];
A.build(1,1,n+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) dp[i][j]=inf;
dp[1][1]=0;
A.update(1,2,2,2*w[1]-2);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) {
if(i==1&&j==1) continue;
Pre=inf;
Pre=min(Pre,A.query(1,l1[i]+1,r1[i]+1,l2[j]+1,r2[j]+1));
if(Pre!=inf) {
dp[i][j]=Pre+w[i]+w[j]-i-j;
A.update(1,i+1,j+1,dp[i][j]+w[i]+w[j]-i-j);
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(dp[i][j]==inf) cout<<"inf ";
else cout<<dp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}