首页 > 代码库 > [51NOD1524] 可除图的最大团(组合,dp)

[51NOD1524] 可除图的最大团(组合,dp)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1524

题意:略。

这个题相当于是找出现最长的整除链。

dp记下输入中每个数出现的次数,枚举1~1e6所有数,再枚举每个数的倍数,假如出现了,直接更新dp数组。

1e6的话筛法大概要运算1e7次,放心做。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int maxn = 1001000;
 6 int n;
 7 int a, dp[maxn];
 8 
 9 inline bool scan_d(int &num) {
10     char in;bool IsN=false;
11     in=getchar();
12     if(in==EOF) return false;
13     while(in!=-&&(in<0||in>9)) in=getchar();
14     if(in==-){ IsN=true;num=0;}
15     else num=in-0;
16     while(in=getchar(),in>=0&&in<=9){
17         num*=10,num+=in-0;
18     }
19     if(IsN) num=-num;
20     return true;
21 }
22 
23 int main() {
24     // freopen("in", "r", stdin);
25     while(~scanf("%d", &n)) {
26         memset(dp, 0, sizeof(dp));
27         for(int i = 1; i <= n; i++) {
28             scan_d(a);
29             dp[a]++;
30         }
31         for(int i = 1; i <= 1000000; i++) {
32             if(!dp[i]) continue;
33             for(int j = 2; j * i <= 1000000; j++) {
34                 if(dp[i*j]) dp[i*j] = max(dp[i*j], dp[i] + 1);
35             }
36         }
37         int ret = 0;
38         for(int i = 1; i <= 1000000; i++) ret = max(ret, dp[i]);
39         printf("%d\n", ret);
40     }
41     return 0;
42 }

 

[51NOD1524] 可除图的最大团(组合,dp)