首页 > 代码库 > [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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。