题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6076
题意：现要检查两条队伍，有两种方式，一种是从两条队伍中任选一条检查一个人，第二种是在每条队伍中同时各检查一个，前提是两条队伍中的两个人的序号大于k。然后询问检查最少需要的时间。
解法：根据题意很容易想到dp[i][j]表示第一个队伍已经检查完前i个人，第二个人已经检查完前j个人所需最小时间。但是这样是O(n^2)毫无疑问会tle。我们发现k很小，所以我们可以对于两种转移方式分开处理。对于差值小于等于k的人可以普通的转移。对于差值大于k的我们可以先预处理出来每个偏移量（第一队列中选的人的位置和第二个队列中选的人的位置的差值）差值小于等于k的点对，然后通过二分找到左边最近的一个差值小于k的点，那么中间按照这个偏移量一对一对的检查，差值一定是大于k的。所以总复杂度O(n * k * log N)。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 60010;
int n, k, a[maxn], b[maxn], pos[maxn];
bool cmp(int x, int y){return x>y;}
vector <int> v[maxn*2];
int dp[maxn][22];
int dfs(int x, int y){
if(!x||!y) return x+y;
if(abs(a[x]-b[y])<=k){
int &g=dp[x][a[x]-b[y]+k];
if(g) return g;
return g = min(dfs(x-1,y),dfs(x,y-1))+1;
}
auto it = lower_bound(v[x-y+n].begin(),v[x-y+n].end(),x,cmp);
if(it == v[x-y+n].end()) return max(x, y);
int t = *it;
return dfs(t, y-x+t)+x-t;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &n,&k);
for(int i=0; i<=2*n; i++) v[i].clear();
memset(dp, 0, sizeof(dp));
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
for(int i=1; i<=n; i++){
scanf("%d", &b[i]);
pos[b[i]] = i;
}
for(int i=n; i>=1; i--){
for(int j=a[i]-k; j<=a[i]+k; j++){
v[i-pos[j]+n].push_back(i); }
}
int ans = dfs(n, n);
printf("%d\n", ans);
}
return 0;
}