HDU 6076 - Security Check | 2017 Multi-University Training Contest 4

/*

HDU 6076 - Security Check [ DP,二分 ]  |  2017 Multi-University Training Contest 4

题意：

	给出两个检票序列 A[N], B[N]

	规定 abs(A[i]-B[j]) <= k 的i,j不能同时检票

	求最少的检票时间

	限制  N<= 6e4, k <= 10

分析：

	f(i,j) 为检票至i,j的时间

	则 f(i,j) = f(i-1,j-1) + 1 ,  abs(A[i]-B[j]) > k

			  = min(f(i-1,j), f(i,j-1)) + 1 , abs(A[i]-B[j]) <= k

	对于第二项，由于k小，可DP

	对于第一项，可以二分最大的 t 使得 f(i,j) = f(i-t,j-t) + t 成立

		那么 f(i-t,j-t) 就是第二项的了

*/

#include <bits/stdc++.h>

using namespace std;

const int N = 60005;

vector<int> G[N<<1];

int dp[N][25];

int a[N], b[N], pos[N];

int t, n, k;

int f(int n, int m)

{

    if (n == 0 || m == 0) return n+m;

    if (abs(a[n]-b[m]) > k)

    {

        int t = lower_bound(G[m-n+N].begin(), G[m-n+N].end(), n) - G[m-n+N].begin();

        if (t == 0) return max(n, m);

        t = G[m-n+N][t-1];

        return f(t, m-n+t) + n-t;

    }

    else

    {

        int t = b[m]-a[n]+k;

        if (dp[m][t] == -1)

            dp[m][t] = min(f(n-1, m), f(n, m-1)) + 1;

        return dp[m][t];

    }

}

int main()

{

    scanf("%d", &t);

    while (t--)

    {

        for (int i = 0; i < N<<1; i++) G[i].clear();

        memset(dp, -1, sizeof(dp));

        scanf("%d%d", &n, &k);

        for (int i = 1; i <= n; i++)

        {

            scanf("%d", &a[i]);

            pos[a[i]] = i;

        }

        for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

        for (int i = 1; i <= n; i++)

            for (int j = max(1, b[i]-k); j <= min(n, b[i]+k); j++)

            {

                G[i-pos[j]+N].push_back(pos[j]);

            }

        for (int i = 0; i < N<<1; i++) sort(G[i].begin(), G[i].end());

        int ans = f(n, n);

        printf("%d\n", ans);

    }

}