Problem
两列队伍，每队 N 人，A 队每人 rank 为
ai
，B 队每人 rank 为
bi
，要求从队首向队尾顺次检查（完成检查的即离队），每次检查可以是下列两种操作的任一种：
任选一个队伍的队首检查（如果该队非空）如果两队队首
∣ai−bi∣>K
，则可以同时检查两队队首。
Limit
1≤N≤60000
1≤k≤10
1≤ai,bi≤N
ai≠aj, bi≠bj
Idea
正常的 dp 思路是:
dp[i][j] 表示 A 队检查了前 i 个人，B 队检查了前 j 个人的最少检查次数。时空复杂度都将达到
O(N2)
将上述 dp 思路在二维坐标看思考（i 为 x 轴，j 为 y 轴）。
则操作 1 等同于 dp[i][j]=min(dp[i][j-1], dp[i-1][j])+1 ，即从正下方点或左点转移。操作 2 等同于 dp[i][j]=min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1 = dp[i-1][j-1]+1 （其中左下点一定小于等于左点与下点），即从左下点转移。 继续深化操作 2 ，dp[i][j] = dp[i-1][j-1]+1 = dp[i-2][j-2]+2 = dp[i-3][j-3]+3 ... ，当点 (i, j) ,(i-1, j-1), (i-2, j-2) … 能够满足操作 2 的转移条件时，可快速跳转，无须中间过程。
由于 K 值较小，故操作 1 的状态有限，上限在
N⋅K
，故利用记忆化搜索，将 dp[n][n] 递归转移，若当前 (i, j) 不满足操作 2 的条件，则暴力判断从正下点或左点转移（最多
O(N⋅K)
）。若满足条件，则找到最大的不满足操作 2 的 (i-k, j-k) ，转移为 dp[i][j] = dp[i-k][j-k]+k 。对于这部分的查找，由于 sub = i-j = (i-k)-(j-k) ，故预先将不满足条件的组合按照 i-j 的差值存储，二分查找对应差值的最大小于 (i, j) 的点。
思路来源
Code
#include<bits/stdc++.h>
using namespace std;
const int N =
60000 +
10;
const int inf =
1e9 +
7;
const int SUBSTRACT =
2*N;
int T, n, k, a[N], b[N], posb[N];
vector<int> v[SUBSTRACT];
map<int, int> dp[N];
bool cmp(
int x,
int y) {
return x > y;
}
void init() {
for(
int i=
0;i<=
2*n;i++)
v[i].clear();
for(
int i=
0;i<=n;i++) dp[i].clear();
}
int dfs(
int x,
int y) {
if(!x || !y)
return x+y;
if(dp[x].find(y) != dp[x].end())
return dp[x][y];
if(
abs(a[x] - b[y]) <= k) {
dp[x][y] = min(dfs(x-
1, y), dfs(x, y-
1)) +
1;
}
else {
int pos = lower_bound(v[x-y+n].begin(), v[x-y+n].end(), x, cmp) - v[x-y+n].begin();
if(pos >= v[x-y+n].size())
return max(x, y);
dp[x][y] = dfs(v[x-y+n][pos], v[x-y+n][pos]-x+y) + x-v[x-y+n][pos];
}
return dp[x][y];
}
int main()
{
scanf(
"%d", &T);
while(T-- &&
scanf(
"%d %d", &n, &k)!=EOF)
{
init();
for(
int i=
1;i<=n;i++)
scanf(
"%d", &a[i]);
for(
int i=
1;i<=n;i++)
{
scanf(
"%d", &b[i]);
posb[ b[i] ] = i;
}
for(
int i=n;i;i--)
for(
int gap=
0;gap<=k;gap++)
{
if(a[i]-gap >
0) v[ i - posb[ a[i]-gap ] + n ].push_back(i);
if(gap && a[i]+gap <= n) v[ i - posb[ a[i]+gap ] + n ].push_back(i);
}
printf(
"%d\n", dfs(n, n));
}
}
