Starters 189-Number Walks

思路讲解

题面总结

给定一个长度为 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

源代码

// 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了。

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<<" ";
}