小米ICPC预选赛-A:数论,dp

68 阅读 0 评论 45 点赞

我是靠谱客的博主碧蓝嚓茶，最近开发中收集的这篇文章主要介绍小米ICPC预选赛-A:数论,dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意:

给你一个序列 $a_1,...,a_n$ .让你从里面选出一个子集 $S$ ,使得子集中任意两个数都互为倍数.求最大子集.( $1e5,a_ileq1e7$ ).

题目思路:

首先，本题的弱化版:https://leetcode-cn.com/problems/largest-divisible-subset/solution/。

整除关系具有传递性,所以任意两个数成倍数关系不妨转化为:【对子集 $S$ 排序后相邻两个数成倍数关系。】

那么有一个很自然的类似LIS的 $O(n^2)$ 填表法.见弱化版。

这里考虑刷表法,令 $d p (i)$ 代表子集中都以i为约数的最大子集.然后用 $d p (i)$ 更新所有 $i$ 的倍数的 $d p$ 值。

根据自然数的倒数的级数定理，该方法的复杂度为: $O (w l o g w)$

进一步优化:只用素数的倍数去更新.

因为一个合数可以由多个素数组成。

例如: 从 $d p (2)$ 转移到 $d p (12)$ .要乘上6.而 $6 = 2 * 3$ .

那么用前者的方法我们可以一步从 $d p (2)$ 到 $d p (12)$ .

用后者的方法是从 $d p (2)$ 到 $d p (6)$ 再到 $d p (12)$ //或者从2到4到12.

所以后者少了很多次无用的转移.具体的,根据素数的倒数的级数定理，该方法的复杂度为: $O (w l o g l o g w)$

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5;
int dp[maxn] , sz[maxn];
int prime[maxn] , cnt;
bool book[maxn];
void init()
{
for (int i = 2 ; i < maxn ; i++){
if (!book[i]) prime[++cnt] = i;
for (int j = 1 ; j <= cnt && 1ll * prime[j] * i < maxn ; j++){
book[prime[j] * i] = 1;
if (i % prime[j] == 0) break;
}
}
}
int main()
{
init();
int n; scanf("%d",&n);
for (int i = 1 ; i <= n ; i++) {
int x;scanf("%d",&x);
sz[x]++;
}
int ans = 0;
int up = 1e7;
for (int i = 1 ; i <= up ; i++){
dp[i] += sz[i];
for (int j = 1 ; j <= cnt && prime[j] * i <= up ; j++)
dp[prime[j] * i] = max (dp[prime[j] * i] , dp[i]);
ans = max (ans , dp[i]);
}
printf("%dn" , ans);
return 0;
}