题意：有两个安检队列，每个队列都有n个人，每个人都有一个权值，同一个队列中不会有两个人权值相同。有一个安检员，如果两个队列的第一个人的权值差大于K，则安检员可以同时检查这两个人，否则只能选择其中一个队列检查第一个人，人被检查完后即出队列。
题解：设 fi,j 表示仅考虑a[1..i]a[1..i]与b[1..j]b[1..j]时，最少需要多少时间。
若 |ai−bj|>k ∣，则 fi,j=fi−1,j−1+1 ，否则 fi,j=min(fi−1,j,fi,j−1)+1 。
注意到后者只有O(nk)个，前者可以通过二分找到最大的t，满足i,j往前t个均不冲突，然后再从某个后者状态转移过来。
二分时记录c[d]记录的是两队列中相隔为d的权值差小于等于K的人的位置
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; #define N 60010 #define mod 1000007 typedef long long ll; struct rec{ ll h; int w; rec(){} rec(ll h,int w):h(h),w(w){} }; int a[N],b[N],id[N]; vector<rec> g[mod]; vector<int> c[N*2]; int ca,n,K; const int inf=0x3f3f3f3f; int get_dp(int x,int y) { ll h=(ll)x*N+y,hm=h%mod; for(int i=0;i<g[hm].size();++i) if(g[hm][i].h==h) return g[hm][i].w; return -1; } void set_dp(int x,int y,int z) { ll h=(ll)x*N+y,hm=h%mod; g[hm].push_back(rec(h,z)); } int dfs(int x,int y) { if(x==0) return y; if(y==0) return x; int ans=get_dp(x,y); if(ans!=-1) return ans; ans=inf; if(abs(a[x]-b[y])<=K) { ans=min(ans,dfs(x-1,y)+1); ans=min(ans,dfs(x,y-1)+1); } else { int d=n+x-y,id,i,sz=c[d].size(); if(sz==0||x<c[d][0]) i=min(x,y); else if(c[d][sz-1]<x) i=x-c[d][sz-1]; else { id=lower_bound(c[d].begin(),c[d].end(),x)-c[d].begin()-1; i=x-c[d][id]; } ans=min(ans,dfs(x-i,y-i)+i); } set_dp(x,y,ans); return ans; } int main() { // freopen("1010.in","r",stdin); scanf("%d",&ca); while(ca--) { for(int i=0;i<mod;++i) g[i].clear(); scanf("%d%d",&n,&K); for(int i=1;i<=2*n;++i) c[i].clear(); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) scanf("%d",&b[i]),id[b[i]]=i; for(int i=1;i<=n;++i) { for(int j=max(1,a[i]-K);j<=min(n,a[i]+K);++j) { int d=n+i-id[j]; c[d].push_back(i); } } printf("%d\n",dfs(n,n)); } return 0; }