题目

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

题解

暴力思路

很显然,用动态规划的思想,有如下递推式
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(n2) 的操作,但是可以发现,它只需要取自己左上的数,也即不考虑差值小于 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 %}