模拟赛题讲解[31]

来自 yukuai26 2023-08-05 noi.ac #3275

题目描述：

给定 $N$个单调递增的数 $A_i$和 $M$个单调递增的数 $B_i$，从 $A$和 $B$中分别找到一个子序列 $a,b$，使得这两个子序列长度一样并且 $a_i-a_{i+1}=b_i-b_{i+1}$。求这两个子序列的最长长度。

输入格式：

第一行两个整数 $N,M$。

接下来一行 $N$个整数代表 $A$。

接下来一行 $M$个整数代表 $B$。

输出格式：

输出一行一个整数代表答案。

输入样例：

5 5
1 2 3 4 5
4 6 7 8 10

输出样例：

4

数据范围：

对于 $100\%$的数据，$1\leq N,M\leq 1000,1\leq A_i,B_j\leq 10000$。

题解：

居然没想到正解，我真是 stupid 啊。

先讲讲暴力dp解法。设 $f_{i,j}$ 表示考虑到 $a$ 的前 $i$ 个数和 $b$ 的前 $j$ 个数，强制选了 $a_i,b_j$ ，直接看代码：

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++) f[i][j] = 1;
for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
        for(int k = 1; k < i; k++)
            for(int l = 1; l < j; l++)
                if(a[i] - a[k] == b[j] - b[l]) up(f[i][j], f[k][l] + 1), up(res, f[i][j]);
cout << res << '\n';

开始讲正解。考虑移项，则 $a_i - b_i = a_{i+1}-b_{i+1}$ 。

因此我们只要去出现次数最大 $a_i-b_i$ 的那些 $i$ 就好了

这样为啥对呢，因为都是单调递增的，所以不会有重复的数，就这么水。

时间复杂度 $\mathcal{O}(n + M)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))
#define M ((int)(2e4 + 55))

int n,m,a[N],b[N],cnt[M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> b[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) ++cnt[a[i] - b[j] + 10000ll];
    cout << *max_element(cnt, cnt + 20000 + 30) << '\n';
    return 0;
}