2D1D
决策单调第一题
传送门
思路
先排个序
定义状态 \(dp[i][j]\) 表示前 \(i\) 个村庄,设置了 \(j\) 个邮局的最小距离和
有朴素的状态转移方程:
\[dp[i][j]=min\{dp[k][j-1]+w[k+1][i]\}
\]
其中,\(w[i][j]\) 表示在区间 \([i,j]\) 设置一个村庄的最小距离和
显然,在区间内村庄位置的中位数设置邮局显然是最优的
显然 \(w[i][j]\) 可以用 \(O(V^2)\) 进行预处理,转移为 \(w[i][j]=w[i][j-1]+a[j]-a[\frac{i+j}{2}]\)
这样我们就得到一个 \(O(V^2P)\) 的做法了
既然是四边形不等式的模板题,当然要用决策单调来做啦
考虑证明 \(w[l][r+1]+w[l+1][r]\le w[l][r]+w[l+1][r+1]\)
显然,有 \(w[l][r+1] - w[l][r]= a[r+1]-a[\frac{l+r+1}{2}]\), \(w[l+1][r+1] - w[l+1][r]= a[r+1]-a[\frac{l+r+2}{2}]\)
两式相减,得
\[(w[l][r+1]+w[l+1][r])-(w[l][r]+w[l-1][r-1])=a[\frac{l+r+2}{2}]-a[\frac{l+r+1}{2}]\ge 0
\]
\[w[l][r+1]+w[l+1][r]\le w[l][r]+w[l+1][r+1]
\]
根据惯例,\(dp[i][j]\) 一定也满足决策单调, 因此有 \(t[i][j-1]\le t[i][j]\le t[i+1][j]\)
(\(t\) 为决策点)
因此,我们考虑逐层 DP
,倒序枚举 \(i\)(因为用到了 \(dp[i+1][j]\))
时间优化到 \(O(V^2+VP)\)
代码
#include
#include
#include
#include
#include
#include
#include
#include