Starters 189-Number Walks · znzryb
## 思路讲解
## 题面总结
给定一个长度为 N 的数组 A，其中 A[i] ∈ [1, K]。需要构造一个排列 B（1 到 N 的排列），使得对于所有 i ∈ [1, K]，满足 A[B[i]] = i。
对于每个起始位置 i（1 ≤ i ≤ N），求出从位置 i 开始构造满足条件的排列 B 时，相邻元素差值绝对值之和的最小值。
换句话说，要最小化 ∑|B[j] - B[j-1]|，其中 B[1] = i，且 A[B[j]] = j。
**输入格式：**
- 第一行：测试用例数 T
- 每个测试用例：
- 第一行：N 和 K
- 第二行：N 个整数表示数组 A
**输出格式：**
对于每个测试用例，输出 N 个整数，第 i 个整数表示从位置 i 开始的最小代价。
**约束条件：**
- 1 ≤ T ≤ 10³
- 1 ≤ K ≤ N ≤ 10⁶
- 1 ≤ A[i] ≤ K
- 保证至少存在一个满足条件的排列 B
虽然不一定选择最靠近的，但是一定是选择右端最靠近或者左端最靠近点的一侧。
这个如何证明那？
那么我们感性的理解，如果在最优序列中，再次移动需要到 j 的各种情况。
那么我们发现，这个 j 落在外面，l，r 中还是必有一个最优，落在里面那更不必多说了。
okay，那我们也算是成功减小了范围，但是还是不知道怎么做呀？~~继续读题解~~
啊哈，那么我们发现那，这其实是一个前缀dp，即状态转移只和前面一个状态相关，那么前面一个状态里只有 l 和 r，那么答案就呼之欲出了，从前面这个来转移。
那么我们用记忆化搜索，可能这个让人更好理解一点。
那么这个正难则反思想是应用于dp的，但是这个dp也有点难写，过了就行，开摆。
## AC代码
[https://www.codechef.com/viewsolution/1167791134](https://www.codechef.com/viewsolution/1167791134)
::: 源代码
```cpp
// Problem: Number Walks
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/NUMBERWALK
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,A[MAXN];
/*
*/
inline void init(){
}
inline void solve(){
cin>>N>>K;
init();
vector<vector<int>> g(K+5);
FOR(i,1,N){
cin>>A[i];
g[A[i]].pb(i);
}
// 要求A[B[i]]==i ，并且使B[i]数组中的数的差值绝对值最小
vector<ll> memo(N+5,INF);
auto dfs=[&](auto &&dfs,ll node,ll val)->ll{
if(memo[node]!=INF) return memo[node];
if(val==K){
memo[node]=0;
return 0;
}
ll v=node;
// #ifdef LOCAL
// debug(node);debug(val);
// #endif
auto it=lower_bound(all(g[val+1]),v);
if(it!=g[val+1].begin()){
auto it_=prev(it);
ll diff=abs(*it_-v);
ll res=dfs(dfs,*it_,val+1);
memo[node]=min(memo[node],diff+res);
}
if(it!=g[val+1].end()){
ll diff=abs(*it-v);
ll res=dfs(dfs,*it,val+1);
memo[node]=min(memo[node],diff+res);
}
return memo[node];
};
FOR(i,1,N){
auto it=lower_bound(all(g[1]),i);
ll ans=INF;
if(it!=g[1].begin()){
auto it_=prev(it);
ll diff=abs(*it_-i);
ll res=dfs(dfs,*it_,1);
ans=min(diff+res,ans);
}
if(it!=g[1].end()){
ll diff=abs(*it-i);
ll res=dfs(dfs,*it,1);
ans=min(diff+res,ans);
}
cout<<ans<<" ";
}
// #ifdef LOCAL
// FOR(i,1,N){
// cerr<<memo[i]<<" ";
// }
// cerr<<"\n";
// #endif
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）
调试的时候发现这里写错了，应该写1，我写成2了。
```cpp
FOR(i,1,N){
auto it=lower_bound(all(g[1]),i);
ll ans=INF;
if(it!=g[1].begin()){
auto it_=prev(it);
ll diff=abs(*it_-i);
ll res=dfs(dfs,*it_,1);
ans=min(diff+res,ans);
}
if(it!=g[1].end()){
ll diff=abs(*it-i);
ll res=dfs(dfs,*it,1);
ans=min(diff+res,ans);
}
cout<<ans<<" ";
}
```