Starters 189-Number Walks

思路讲解

虽然不一定选择最靠近的，但是一定是选择右端最靠近或者左端最靠近点的一侧。

这个如何证明那？

那么我们感性的理解，如果在最优序列中，再次移动需要到 j 的各种情况。

从图中可以看出，l‘不优，即便是在 j 位于l’ 与 x之间的时候

那么我们发现，这个 j 落在外面，l，r 中还是必有一个最优，落在里面那更不必多说了。

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了。（第7行，也就是res那行）

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