题目

{% fold 点击显/隐题目 %}

In airport of Bytetown, there are two long queues waiting for security check. Checking a person needs one minute, and two queues can be checked at the same time.

Two teams $A$ and $B$ are going to travel by plane. Each team has $n$ players, ranked from $1$ to $n$ according to their average performance. No two players in the same team share the same rank. Team $A$ is waiting in queue $1$ while team $B$ is waiting in queue $2$ . Nobody else is waiting for security check.

Little Q is the policeman who manages two queues. Every time he can check one person from one queue, or check one each person from both queues at the same time. He can't change the order of the queue, because that will make someone unhappy. Besides, if two players $A_i$ and $B_j$ are being checked at the same time, satisfying $|A_i-B_j|\leq k$ , they will make a lot of noise because their rank are almost the same. Little Q should never let that happen.

Please write a program to help Little Q find the best way costing the minimum time.

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases.

In each test case, there are $2$ integers $n,k(1\leq n\leq 60000,1\leq k\leq 10)$ in the first line, denoting the number of players in a team and the parameter $k$ .

In the next line, there are $n$ distinct integers $A_1,A_2,...,A_n(1\leq A_i\leq n)$ , denoting the queue $1$ from front to rear.

Then in the next line, there are $n$ distinct integers $B_1,B_2,...,B_n(1\leq B_i\leq n)$ , denoting the queue $2$ from front to rear.

For each test case, print a single line containing an integer, denoting the minimum time to check all people.

1 4 2 2 3 1 4 1 2 4 3

7

{% endfold %}

题解

暴力思路

很显然,用动态规划的思想,有如下递推式
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
其中 dp[i][j] 表示第一队前 i 个人和第二队前 j 个人,最小的检查时间

然后就会发现一个问题, n 最大能达到 60000 空间时间都会超过限制

首先来解决存储的问题
很容易发现,这道题有个很关键的地方: k最大只到10

又因为每个数字在每个队伍里只出现一次,那么可以得知只有极少数的人没有办法一起检查
也即只有极少数的 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 操作
而大多数都是取 dp[i][j] = dp[i-1][j-1] + 1

那么就可以单独考虑两种情况
针对前一种情况,可以用记忆化搜索来做
这里有一个非常好的转换:

直接存储 dp[i][j] 显然是存不下的,但是我们可以发现,当前的前提是 abs(a[i]-b[j]) <= k (需要特别注差值是指权值而不是位置)
而 k 又是一个非常小的数字
我们完全可以只记录 i 和 a[i]-a[j]+k 这样我们只需要一个 60000*20 的数组
(这里 +k 是为了保证为正数)

这样,就能在 O(nk) 的时间处理好这一部分了

然后来看另一部分
可以知道这一部分就是 dp[i][j] = dp[i-1][j-1] + 1
看上去是 O(n²) 的操作,但是可以发现,它只需要取自己左上的数,也即不考虑差值小于 k 的情况下可以在 O(n) 的时间内找出答案
而差值不小于 k 的情况我们已经计算完毕了
因此完全可以用递归求出这一部分的内容(可以证明没有存在多次计算同一状态)

题解的思路

关于题解的解法,前一部分是一样的
不一样的是后一部分
思路也比较独特

(i,j)表示第一队第i个人和第二队第j个人,当发现他们的差值大于k时
我们可以给他们连一条线(表示一起检查),然后把线向左平移,直到线两端的人差值小于等于k
此时记两个人的位置为(a,b)
然后这两个线中间的位置显然是可以一起检查
那么 dp[i][j] = dp[a][b] + i - a

问题就转换成如何找到最近的符合要求的平行线段了
很明显,平行意味着 i-j 相等
那么可以在读入的时候先预处理所有的线段间距
由于只需要找间距小于等于 k 的,因此我们只需要对每一个 i 枚举 k 即可
然后将数据存入 vector 二分查找即可

这里需要注意的是
lower_bound() 找的是第一个小于等于的位置,与我们的要求不符
我们应该让 vector 递增记录,然后给 lower_bound() 传入一个 max() 的比较函数

代码

暴力思路

{% fold 点击显/隐代码 %}```cpp Security Check 暴力 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
using namespace std;

const int maxn = 60005;
const int maxk = 11;

int queue_a[maxn], queue_b[maxn];
int DP[maxn][maxk << 2];
int n, k;

void init() { memset(DP, -1, sizeof(DP)); }

int dfs(int apos, int bpos) {
int RETURN = -1;
if (!apos || !bpos) {
RETURN = apos | bpos;
} else {
if (abs(queue_a[apos] - queue_b[bpos]) <= k) {
//暴力
int &dp = DP[apos][queue_a[apos] - queue_b[bpos] + k];
if (dp == -1)
dp = min(dfs(apos - 1, bpos), dfs(apos, bpos - 1)) + 1;
RETURN = dp;
} else {
RETURN = dfs(apos - 1, bpos - 1) + 1;
}
}
return RETURN;
}

int main() {
// freopen("out.txt", "w", stdout);
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);

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

    printf("%d\n", dfs(n, n));
}
return 0;

}

{% endfold %}


## 题解思路
{% fold 点击显/隐代码 %}```cpp Security Check 题解思路 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;


const int maxn = 60005;
const int maxk = 15;

int queue_a[maxn], queue_b[maxn];
int bposList[maxn];

int DP[maxn][maxk << 2];
vector<int> DisList[maxn << 2];

int n, k;

bool cmp(int a, int b) { return a > b; }

void init() {
    memset(DP, -1, sizeof(DP));
    for (int i = 0; i <= n << 2; ++i)
        DisList[i].clear();
}

int dfs(int apos, int bpos, int deep) {
    int RETURN = -1;
    if (!apos || !bpos) {
        RETURN = apos | bpos;
    } else {
        if (abs(queue_a[apos] - queue_b[bpos]) <= k) {
            //暴力
            int &dp = DP[apos][queue_a[apos] - queue_b[bpos] + k];
            if (dp == -1) {
                dp = min(dfs(apos - 1, bpos, deep + 1),
                         dfs(apos, bpos - 1, deep + 1)) +
                     1;
            }
            RETURN = dp;
        } else {
            int dis = apos - bpos + n;
            vector<int> &List = DisList[dis];
            vector<int>::iterator it =
                lower_bound(List.begin(), List.end(), apos, cmp);
            if (it == List.end() || *it == apos) {
                RETURN = max(apos, bpos);
            } else {
                int lastapos = *it;
                RETURN = dfs(lastapos, bpos - apos + lastapos, deep + 1) +
                         apos - lastapos;
            }
        }
    }
    return RETURN;
}

int max(int a, int b) { return a > b ? a : b; }

int main() {
    // freopen("out.txt", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);

        init();
        for (int i = 1; i <= n; i++)
            scanf("%d", &queue_a[i]);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &queue_b[i]);
            bposList[queue_b[i]] = i;
        }


        for (int apos = n; apos >= 1; --apos) {
            int a = queue_a[apos];
            for (int b = a - k; b <= a + k; ++b) {
                int bpos = bposList[b];
                int dis = apos - bpos + n;
                DisList[dis].push_back(apos);
            }
        }

        printf("%d\n", dfs(n, n, 1));
    }
    return 0;
}

{% endfold %}

HDU 6076.Security Check