UVA12170 Easy Climb 题解
分析
老样子,先判断无解情况。
我们假设 \(h_n\) 无限高于或者低于 \(h_1\),那么中间的那些都必须尽力去逼近 \(h_n\),一定是递增或递减的。但由于相邻的两堆石头高度差不能超过 \(d\),所以递增或递减的最大长度为 \((n-1) \cdot d\)。如果 \(|h_n-h_1| > (n-1) \cdot d\),那么肯定是无解。反过来想,如果不大于,那么一定存在合法的构造方法,即一定有解。
手算以下不难发现,对于每一个 \(i\),都有 \[ h_i' \in [\max{(h_{i-1},h_{i+1})-d,\min{(h_{i-1},h_{i+1})+d}}] \] 那么如果 \(h_i\) 不在区间内,将其变为距离它最近的区间边界是最优的,因为差值最小。
如果 \(h_i\) 在区间内,那么可以让它不变,这样贡献为 0。
如果这样去做了,那么对于每个 \(h_i '\),都能写成 \(h_x+kd \quad (x \in [1,n],k \in [-n,n])\) 的形式。
感性证明一下,如果改变 \(h_i\) 的值,那么一定是在某个现有的 \(h_i\) 或 \(h_i'\) 的基础加上过减去 \(d\);如果不改变,令 \(k=0\) 即成立。严格证明可以用归纳法,这里不再赘述。
所以所有可能的值的个数为 \(2n^2\),记为 \(a\)。
设 \(f(i,j)\) 表示前 \(i\) 堆石头,第 \(i\) 堆的高度为 \(j\) 时,所需要的最小代价。
边界
\[ f(i,j) = \begin{cases} 0 & i=0,j=h_1 \\ \inf & \text{otherwise} \end{cases} \]
转移
\[ f(i,j) = \min \limits_{j-d \le k \le j+d} { \{ f(i-1,k)+ |a_i-j| \} } \]
\[ f(i,j) = \min_{j-d \le k \le j+d} { \{ f(i-1,k) \} } + |a_i - j| \]
滚动数组+单调队列优化即可。
最终答案 \[ ans= \max{\{ f(n-1,i) \}} \quad |h_n-i| \le d \]
由于 \(j\) 这一维值域过大,具体实现时可以离散化,这一维存下标。
状态数 \(n^2\) 个,决策 \(n\) 个,转移 \(O(1)\),总复杂度 \(O(n^3)\)。
CODE
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N=105, M=N*N*2;
int t, n, m, d, h[N], q[M];
ll ans, a[M], f[2][M];
inline void init() {
for(int i=1;i<=n;++i) {
for(int j=-n;j<=n;++j) if(h[i]+j*d>=0) // 高度不会小于0
a[++m]=h[i]+j*d;
}
sort(a+1,a+m+1);
m=unique(a+1,a+m+1)-a-1;
for(int i=1;i<=n;++i) h[i]=lower_bound(a+1,a+m+1,h[i])-a;
// 离散化去重,现在和h[i]存的是原来h[i]在a中的位置。
}
inline void sol() {
m=0, ans=1e15;
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&d);
for(int i=1;i<=n;++i) scanf("%d",&h[i]);
if(abs(h[1]-h[n])>(n-1)*d) { puts("impossible"); return; }
// 无解
init();
int p=1;
f[0][h[1]]=0;
for(int i=2;i<n;++i) {
int k=0, l=1, r=0;
for(int j=1;j<=m;++j) {
while(l<=r&&a[q[l]]<a[j]-d) ++l;
// 排除不合法(越界)的决策。
while(k<=m&&a[k+1]<=a[j]+d) {
++k;
while(l<=r&&f[p^1][q[r]]>=f[p^1][k]) --r;
// 维护决策单调增
q[++r]=k;
}
if(l<=r) f[p][j]=f[p^1][q[l]]+abs(a[h[i]]-a[j]);
// 队头即使最优决策。
}
p^=1;
}
for(int i=1;i<=m;++i) if(abs(a[h[n]]-a[i])<=d)
ans=min(ans,f[p^1][i]);
printf("%lld\n",ans);
}
int main() { for(scanf("%d",&t);t--;sol()); }