B - Dividing Subsequence

题意：

数组a和数组b，找出最长公共子序列，使得每个b[ i ] 都是 a[ i ]的倍数。

思路：

AtCoder Regular Contest 133 B(最长上升子序列) C(思维) - 知乎

这种题应把问题转化，把 要找的 和 找的条件 给分离了 。

有空再补。

代码：

#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;
}