[hdu7097]Just a Data Structure Problem

(四边形不等式的套路题)

对于某一组$a_{i}$,显然可以区间dp,设$f_{l,r}$表示区间$[l,r]$​的答案,则转移即
$$
f_{l,r}=\begin{cases}0&(l=r)\\\sum_{i=l}^{r}\sum_{j=l}^{r}dist(a_{i},a_{j})+\min_{l\le i<r}(f_{l,i}+f_{i+1,r})&(l<r)\end{cases}
$$
为了方便,对于$l<r$定义$f_{l,r}$的最优决策为后者取到$\min$时的(任意一个)$i$

记$S_{l,r}=\sum_{i=l}^{r}\sum_{j=l}^{r}dist(a_{i},a_{j})$,不难发现其满足单调性四和边形不等式,即
$$
\forall a_{1}\le a_{2}\le b_{1}\le b_{2},\begin{cases}S_{a_{2},b_{1}}\le S_{a_{1},b_{2}}\\S_{a_{1},b_{1}}+S_{a_{2},b_{2}}\le S_{a_{1},b_{2}}+S_{a_{2},b_{1}}\end{cases}
$$
由此,我们就可以得到$f$满足四边形不等式,证明如下——

引理1:$f$满足四边形不等式当且仅当$\forall a<b,f_{a,b}+f_{a+1,b+1}\le f_{a,b+1}+f_{a+1,b}$

若$a+1<b$,即有$f_{a+1,b}+f_{a+2,b+1}\le f_{a+1,b+1}+f_{a+2,b}$

将两式相加,消项后即有$f_{a,b}+f_{a+2,b+1}\le f_{a,b+1}+f_{a+2,b}$

不难发现记将$a+1$变为了$a+2$,以此类推即有$f_{a_{1},b}+f_{a_{2},b+1}\le f_{a_{1},b+1}+f_{a_{2},b}$

类似地,也可以将$b+1$变为$b+2$,以此类推即得到四边形不等式

另外,对于$a_{1}=a_{2}$或$b_{1}=b_{2}$的情况,四边形不等式显然成立

此时即只有两维,对$b-a$归纳,在$b-a\le 2$时简单分析显然成立

若$b-a<k$时成立,考虑$b-a=k$时:

设$f_{a,b+1}$的最优决策为$x$,$f_{a+1,b}$的最优决策为$y$,不妨假设$x\le y$(对于$x>y$​是类似地),即有
$$
f_{a,b+1}+f_{a+1,b}=(f_{a,x}+f_{x+1,b+1}+S_{a,b+1})+(f_{a+1,y}+f_{y+1,b}+S_{a+1,b})
$$
而对于$f_{a,b}$和$f_{a+1,b+1}$,显然该处决策也对其取$\min$​,即有
$$
f_{a,b}+f_{a+1,b+1}\le (f_{a,x}+f_{x+1,b}+S_{a,b})+(f_{a+1,y}+f_{y+1,b+1}+S_{a+1,b+1})
$$
将两者比较,消掉相同项以及$S$​的四项(对应其四边形不等式),即求证
$$
f_{x+1,b+1}+f_{y+1,b}\le f_{x+1,b}+f_{y+1,b+1}
$$
不难发现这也即为四边形不等式,由归纳显然成立

综上,即证明了$f$满足四边形不等式

引理2:若$f$满足四边形不等式,则$f$具有决策单调性

首先,来解释一下此处的"决策单调性":令$g_{l,r}$为$[l,r]$处的最优决策,则$g_{l,r-1}\le g_{l,r}\le g_{l+1,r}$

不妨考虑$g_{l,r-1}\le g_{l,r}$(对于$g_{l,r}\le g_{l+1,r}$是类似地),令$j=g_{l,r-1}$,也即求证$\forall l\le i<j$(对于$f_{l,r}$)在i处转移不如在$j$处转移,显然由此即可得到$j\le g_{l,r}$

具体的,已知$f_{l,j}+f_{j+1,r-1}\le f_{l,i}+f_{i+1,r-1}$,构造$f_{i+1,r-1}+f_{j+1,r}\le f_{i+1,r}+f_{j+1,r-1}$(根据f的四边形不等式),将两者相加即$f_{l,j}+f_{j+1,r}\le f_{l,i}+f_{i+1,r}$,也即所求证

由此,枚举的范围变为$[g_{l,r-1},g_{l+1,r}]$,将长度求和即$\sum_{l=1}^{n}\sum_{r=l+1}^{n}(g_{l+1,r}-g_{l,r-1})\le \sum_{l=1}^{n}g_{l,n}$,后者显然为$o(n^{2})$,也即可$o(n^{2})$求出初始$a_{i}$的dp数组

下面,考虑如何修改:假设加入元素后序列长度为$n$,相比原来要额外求出的即$\forall 1\le i\le n,f_{i,n}$,显然其仍满足$g_{i,n-1}\le g_{i,n}\le g_{i+1,n}$,但此时长度求和后并不能相消,由于均摊会使得其退化到$o(rn^{2})$

下面,考虑更严格的单调性——若对于$l\le x<y<r$对$f_{l,r}$在$x$处不如$y$处,则对$f_{l-1,r}$在$x$处也不如$y$处

(事实上,满足决策单调性的通常都满足此性质)

由此,从后往前处理出$g_{i,n}$(被划分为若干个区间),并通过二分来求出当前加入位置的影响即可

综上,总复杂度为$o(m^{2}+n^{2}+rn\log n)$,可以通过

[hdu7097]Just a Data Structure Problem[hdu7097]Just a Data Structure Problem
  1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 2005
4 #define M 305
5 #define ll long long
6 struct Edge{
7 int nex,to,len;
8 }edge[N<<1];
9 deque<int>Q;
10 int t,n,q,E,x,y,head[N],l[M],a[M][N],pos[M][N],L[N],R[N],g[N][N];
11 ll d[N][N],S1[N][N],S2[M][N],f[N][N],F[M][N];
12 void add(int x,int y,int z){
13 edge[E]=Edge{head[x],y,z};
14 head[x]=E++;
15 }
16 void dfs(int k,int fa,ll s,int st){
17 d[st][k]=s;
18 for(int i=head[k];i!=-1;i=edge[i].nex)
19 if (edge[i].to!=fa)dfs(edge[i].to,k,s+edge[i].len,st);
20 }
21 ll get_S(int i,int x,int y){
22 if (x>y)return 0;
23 if (y<=l[0])return S1[x][y];
24 return S2[pos[i][y]][x];
25 }
26 ll get_f(int i,int x,int y){
27 if (y<=l[0])return f[x][y];
28 return F[pos[i][y]][x];
29 }
30 ll calc(int i,int j,int k){
31 if (j>=k)return 1e18;
32 return get_f(i,j,k-1)+F[i][k]+S2[i][j];
33 }
34 int main(){
35 scanf("%d",&t);
36 while (t--){
37 scanf("%d%d%d",&n,&l[0],&q);
38 E=0;
39 memset(head,-1,sizeof(head));
40 for(int i=1;i<=n;i++){
41 scanf("%d%d",&x,&y);
42 add(x,i,y),add(i,x,y);
43 }
44 for(int i=0;i<=n;i++)dfs(i,-1,0,i);
45 for(int i=1;i<=l[0];i++)scanf("%d",&a[0][i]);
46 for(int i=1;i<=l[0];i++)S1[i][i]=f[i][i]=0;
47 for(int i=l[0];i;i--){
48 ll s=0;
49 for(int j=i+1;j<=l[0];j++){
50 s+=d[a[0][i]][a[0][j]];
51 S1[i][j]=S1[i+1][j]+s;
52 if (i+1==j){
53 g[i][j]=i;
54 f[i][j]=S1[i][j];
55 }
56 else{
57 f[i][j]=1e18;
58 for(int k=g[i][j-1];k<=g[i+1][j];k++)
59 if (f[i][k]+f[k+1][j]+S1[i][j]<f[i][j]){
60 g[i][j]=k;
61 f[i][j]=f[i][k]+f[k+1][j]+S1[i][j];
62 }
63 }
64 }
65 }
66 printf("%lld\n",(f[1][l[0]]<<1));
67 for(int i=1;i<=q;i++){
68 scanf("%d%d",&x,&y);
69 l[i]=l[x];
70 for(int j=1;j<=l[i];j++){
71 a[i][j]=a[x][j];
72 pos[i][j]=pos[x][j];
73 }
74 a[i][++l[i]]=y,pos[i][l[i]]=i;
75 ll s=S2[i][l[i]]=F[i][l[i]]=0;
76 L[l[i]]=1,R[l[i]]=l[i];
77 Q.clear(),Q.push_back(l[i]);
78 for(int j=l[i]-1;j;j--){
79 s+=d[a[i][j]][y];
80 S2[i][j]=get_S(i,j,l[i]-1)+s;
81 while ((!Q.empty())&&(j<L[Q.front()]))Q.pop_front();
82 F[i][j]=calc(i,j,Q.front());
83 while ((!Q.empty())&&(calc(i,R[Q.back()],j)<calc(i,R[Q.back()],Q.back())))Q.pop_back();
84 if (Q.empty())L[j]=1,R[j]=j;
85 else{
86 int p=Q.back(),l=L[p],r=R[p];
87 while (l<r){
88 int mid=(l+r>>1);
89 if (calc(i,mid,p)<calc(i,mid,j))r=mid;
90 else l=mid+1;
91 }
92 L[Q.back()]=l;
93 if (l==1)continue;
94 L[j]=1,R[j]=l-1;
95 }
96 Q.push_back(j);
97 }
98 printf("%lld\n",(F[i][1]<<1));
99 }
100 }
101 return 0;
102 }
上一篇:[hdu7099]Just Another Data Structure Problem


下一篇:HDU 6649 Data Structure Problem(凸包+平衡树)