这个帖子。

转移的时候，题解区都是 $abs(X_i-Y_j)$ 算代价的，为啥这样可以通过？

难道不需要先处理一下每只猴子到哪一棵大树最优吗？

我是这么写的，也通过了。

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define int long long
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
#define pc putchar
int in(){
	char a=getchar();int k=0,kk=1;
	while(!(a>='0'&&a<='9')) {if(a == '-') kk = -1;a = getchar();}
	while(a>='0'&&a<='9') k = k*10 + a - '0', a = getchar();
	return k*kk;
}
void out(int a){
	if(a < 0) pc('-'), a= -a;
	if(a > 9) out(a/10);
	pc('0'+a%10);
}
#define fst first
#define snd second
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rrep(i,a,b) for(int i=(a);i>=(b);--i)
#define _reps(i,a,b,c) for(int i=(a);i<=(b);c)
#define _rreps(i,a,b,c) for(int i=(a);i>=(b);c)
#define _graph(i) for(int i=head[u];i;i=e[i].nxt)
#define mp make_pair
#define pint pair<int,int>
#define i128 __int128
#define i64 long long
#define pb emplace_back
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define nowtime (double)clock()/CLOCKS_PER_SEC
const int N = 5e3 + 5;
int n,m,X[N],Y[N],f[N],s[N],ff[N];
signed main(){
	n = in();
	_rep(i,1,n) X[i] = in();
	m = in();
	_rep(i,1,m) Y[i] = in();
	sort(X+1,X+1+n), sort(Y+1,Y+1+m);
	_rep(i,1,n){
		s[i] = lower_bound(Y+1,Y+1+m,X[i]) - Y;
//		cout << s[i] << " ";
		s[i] = min(s[i],m);
		s[i] = min( abs(Y[s[i]] - X[i]), s[i] == 1 ? (int)1e18 :  abs(X[i] - Y[s[i]-1]));
//		out(s[i]), pc(' ');
	}
	_rep(i,1,n){
		_rep(j,1,m){
			ff[j] = f[j];
		}
		_rep(j,1,m){
			if(i < j){
				f[j] = 1e18; continue;
			}
			if(j == 1){
				f[j] = ff[j] + abs(X[i]-Y[j]);
				continue;
			}
			f[j] = min(ff[j] + s[i], ff[j-1] + abs(X[i]-Y[j])); // this
//			cout << i << " " << j << " " << f[i][j] << endl;
		}
	}
	out(f[m]);
	return 0;
}