简要题意

线段上有 \(V\) 个村庄，现在要建 \(P\) 个邮局，使每个村庄到最近的邮局的距离之和最小。

50分做法

设\(dp[i][j]\) 表示第一个村庄到第 \(i\) 个村庄，建了 \(j\) 个邮局的最小距离，不难得出状态转移方程：
\(dp[i][j]=min(dp[k][j-1]+w[k+1][i])\)，
其中 \(w[i][j]\) 表示在第 \(i\) 和 \(j\) 个村庄之间建一个邮局的最短总距离。
根据初中知识不难求得，邮局建在第 \(i\) 到 \(j\) 个村庄的中位数的位置上（奇数个村庄）或第 \(i\) 到 \(j\) 个村庄的两个中位数之间（偶数个村庄），则总距离最短，因此我们可以递推求出 \(w[i][j]\)，\(w[i][j]=\begin{cases} & 0\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ } i=j \\ & w[i][j-1]+v[j]-v[(i+j)/2] \text{ }\text{ }\text{ }\text{ }\text{ }i<j\end{cases} \text{ }\) ，其中 \(v[i]\) 表示第 \(i\) 个村庄的位置。

证明：

当第 \(i\) 到 \(j\) 个村庄为奇数个时，第 \(i\) 到 \(j-1\) 个村庄为偶数个，第 \(i\) 到 \(j-1\) 个村庄的中位数为第 \(\left \lfloor \frac{(i+j-1)}{2} \right \rfloor\) 个村庄和第 \(\left \lceil \frac{(i+j-1)}{2} \right \rceil\) 个村庄，第 \(i\) 到 \(j\) 个村庄的中位数为第 \(\frac{(i+j)}{2}\) 即 \(\left \lceil \frac{(i+j-1)}{2} \right \rceil\) 个村庄；
当第 \(i\) 到 \(j\) 个村庄为偶数个时，第 \(i\) 到 \(j-1\) 个村庄为奇数个，第 \(i\) 到 \(j-1\) 个村庄的中位数为第 \(\frac{(i+j-1)}{2}\) 个村庄，第 \(i\) 到 \(j\) 个村庄的中位数为第 \(\left \lfloor \frac{(i+j)}{2} \right \rfloor\) 即 \(\frac{(i+j-1)}{2}\) 个村庄和第 \(\left \lceil \frac{(i+j)}{2} \right \rceil\) 个村庄；
此时第 \(i\) 到 \(j-1\) 个村庄到邮局的距离之和不变，第 \(j\) 个村庄到邮局的距离即第 \(j\) 个村庄到第 \(i\) 到 \(j\) 个村庄的中位数的距离，即第 \(j\) 个村庄的位置减去第 \(i\) 到 \(j\) 个村庄的中位数的位置。

预处理 \(w[i][j]\) 之后，我们可以三层循环分别枚举 \(i,j,k\)，时间复杂度为 \(O(V^{2}P)\) ，无法通过大数据。

满分做法

这是一道DP数组二维的区间DP，并且状态转移方程为 \(dp[i][j]=dp[i][k]+dp[k+1][j]+w[i][j]\) 的形式，因此考虑四边形不等式优化。

四边形不等式定义：

如果对于任意的 \(A\leq B\leq C\leq D\)，均满足 \(w[A][C]+w[B][D]\leq w[A][D]+w[B][C]\)，则称 \(w\) 满足四边形不等式。

证明：

在这一题中，根据 \(w[i][j]\) 的递推式，可得
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }w[i][j+1]-w[i][j]=v[j+1]-v[(i+j+1)/2]\)，
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }w[i+1][j+1]-w[i+1][j]=v[j+1]-v[(i+j+2)/2]\)，
两者相减，得
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }w[i][j+1]-w[i][j]-(w[i+1][j+1]-w[i+1][j])\)
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }=v[j+1]-v[(i+j+1)/2]-(v[j+1]-v[(i+j+2)/2])\)
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }=v[j+1]-v[(i+j+1)/2]-v[j+1]+v[(i+j+2)/2]\)
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }=v[(i+j+2)/2]-v[(i+j+1)/2]\geq 0\)，
则
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }w[i][j+1]-w[i][j]-(w[i+1][j+1]-w[i+1][j])\geq 0\)，
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }w[i][j+1]-w[i][j]-w[i+1][j+1]+w[i+1][j]\geq 0\)，
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }w[i][j]+w[i+1][j+1]\leq w[i][j+1]+w[i+1][j]\)，
\(w\) 满足四边形不等式，则 \(dp\) 同样满足四边形不等式，设 \(s[i][j]\) 为 \(dp[i][j]\) 的最优决策点 \(k\)，可得\(s[i][j]\)单调，即\(s[i][j]\leq s[i][j+1]\leq s[i+1][j+1]\)，\(s[i][j-1]\leq s[i][j]\leq s[i+1][j]\)（这一点的证明后面会提到），每次让 \(k\) 在 \(s[i][j-1]\) 到 \(s[i+1][j]\) 的范围内枚举，就将原本 \(O(V^{2}P)\) 的DP变为 \(O(VP)\) 的了，可以AC，注意此时 \(i\) 需要倒着枚举，因为需要用到 \(s[i+1][j]\)。

对 \(s[i][j-1]\leq s[i][j]\leq s[i+1][j]\) 的证明

假设状态规划方程是 \(dp[i][j]=dp[i][k]+dp[k+1][j]+w[i][j]\) 的形式，设 \(y\) 为使 \(dp[i][j-1]\) 最小的 \(k\)，即 \(s[i][j-1]\)，令 \(x<y\)，有 \(x+1\leq y+1\leq j-1<j\)，根据四边形不等式，得
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }dp[x+1][j-1]+dp[y+1][j]<=dp[y+1][j-1]+dp[x+1][j]\)，

\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }dp[i][x]+dp[x+1][j-1]+w[i][j-1]+dp[i][y]+dp[y+1][j]+w[i][j]<=\)
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }dp[i][x]+dp[x+1][j]+w[i][j]+dp[i][y]+dp[y+1][j-1]+w[i][j-1]\)，

\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }dp[i][j-1](k=x)+dp[i][j](k=y)<=dp[i][j](k=x)+dp[i][j-1](k=y)\)，
\(\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }dp[i][j-1](k=x)-dp[i][j-1](k=y)<=dp[i][j](k=x)-dp[i][j](k=y)\)，
不等式左右两边显然都大于0（\(y\) 是最优决策点，\(dp[i][j]\) 的值最小），所以 \(dp[i][j]\) 的最优决策点一定不是任意一个 \(x\)，即 \(s[i][j]\geq s[i][j-1]\)（即 \(y\)），同理可证\(s[i][j]\leq s[i+1][j]\)。

细节

  • 在预处理前需要对 \(v\) 进行排序，保证 \(v[i]\) 的单调（递增）性，否则 \(w[i][j]\) 就不满足四边形不等式，也就无法使用四边形不等式优化了，然而这题数据较水，给出的 \(v[i]\) 本身就是单调递增的，无需排序（别问我怎么知道的）。
  • DP数组要初始化成INF，且\(dp[i][1]=w[1][i]\)，DP时 \(j\) 从 \(2\) 开始枚举，否则会使用 \(s[i][0]\) 和 \(dp[k][0]\)。
  • 注意 \(s\) 的边界值：\(s[i][1]=1\)（只建1个邮局时最佳划分点只能是第一个村庄），\(s[v+1][i]=v-1\)（倒序枚举 \(dp[i][j]\) 中的 \(i\)，\(v-1\) 即最佳决策点 \(k\) 范围的初始值）。

代码

#includeusing namespace std;const int INF=0x3f3f3f3f;int v,p,a[3005],w[3005][3005],f[3005][3005],s[3005][3005],i,j,k;int main(){ios::sync_with_stdio(false);cin>>v>>p;for(i=1;i>a[i];//输入//这里本应有sort，但是本题数据过水，a[i]本来就单调递增for(i=1;i<v;++i)for(j=i+1;j>1];//预处理w[i][j]//下面几行都是预处理for(i=1;i<=v;++i)for(j=1;j<=p;++j)f[i][j]=INF;for(i=1;i<=v;++i)f[i][1]=w[1][i],s[i][1]=1;for(i=1;i<=p;++i)s[v+1][i]=v-1;//上面几行都是预处理for(i=2;i=i;j--)//倒序枚举村庄for(k=s[j][i-1];k<=s[j+1][i];++k)//四边形不等式优化if(f[k][i-1]+w[k+1][j]<f[j][i])f[j][i]=f[k][i-1]+w[k+1][j],s[j][i]=k;//记得更新最优决策点cout<<f[v][p]<<endl;return 0;}