目录
题意：
数组a和数组b，找出最长公共子序列，使得每个b[ i ] 都是 a[ i ]的倍数。
思路：
AtCoder Regular Contest 133 B(最长上升子序列) C(思维) - 知乎
这种题应把问题转化，把 要找的 和 找的条件 给分离了 。
示例:
我们给第二个数组的每个数开个vector，用来存在第一个数组中可以配对的数的下标，也就是上图。
通过遍历第一个数组，并将下标push给自己倍数的在第二个数组位置的vector来完成的。
此步只完成“配对”。
然后遍历第二个数组，并让配对的下标升序即可。
（在第二个数组中挑几个 —— 第二个数组的子序列。
然后这几个的配对也是顺序 —— 第一个数组的子序列
配对 —— 满足条件）
代码：
#define ll long long
#define endl "\n"
//#define int long long
const int maxn = 5e5 + 5;
int n = 1e5;
int arr1[maxn], id[maxn],ans[maxn];
vector<int>g[maxn];
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> arr1[i];
for (int i = 0; i < n; i++)
{
int tmp;
cin >> tmp;
id[tmp] = i;//记录这个数tmp在数组2的下标
}
for (int i = 0; i < n; i++)
{
for (int j = arr1[i]; j <= n; j+=arr1[i])
{
//给我们的倍数 我们的下标
g[id[j]].push_back(i);
}
}
//lis
ans[0] = -1;
int len = 0;
for (int i = 0; i < n; i++)
{
reverse(g[i].begin(), g[i].end());
for (int j = 0; j < g[i].size(); j++)
{
int aim = g[i][j];
if (aim > ans[len])
{
ans[++len] = aim;//""
}
else
{
//找第一个比他大的
int l = 1, r = len;
while (l < r)
{
int m = l + (r - l) / 2;
if (ans[m] >= aim)
r = m;
else l = m+1;
}
if (ans[r] > aim)
ans[r] = aim;
}
}
}
cout << len << endl;
}
signed main()
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
//cin >> t;
while (t--)
{
solve();
}
return 0;
}
