模拟赛题讲解[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;
}