首页 > 代码库 > DP Good Sequences
DP Good Sequences
给N个升序的数字,要求找出一个子串,每相邻两个数字不互质,求最长串的长度
提示
1)dp[i]表示到第i个数字的最长串
2)dp[i]用前i-1项中与第i项不互质的最大项更新
3)寻找与第i项不互质,即找与第i项有公公因数,所以建立数组dig[i]表示该因数出现的次数
#include <stdio.h> #include <string.h> #define maxn 100005 int dp[maxn]; int dig[maxn]; int mark[maxn]; int gcd(int a,int b) { int k; while(b!=0) { k=a%b; a=b; b=k; } return a; } int max(int a,int b) { return a<b?b:a; } int find(int a) { int maxx=0; if(a==1||a==2||a==3) { dig[a]++; return 1; } int i=0,j=2; int flag=1; while(j*j<=a) { if(a%j==0) { dig[j]++; flag=0; if(j*j!=a) dig[a/j]++; maxx=max(max(maxx,dig[j]),dig[a/j]); } j++; } j=2; while(j*j<=a) //将所有第i项的因数出现次数更新为最大值!!! { if(a%j==0) { dig[j]=maxx; if(j*j!=a) dig[a/j]=maxx; } j++; } if(flag==1) //素数的dig[a]直接加1 { dig[a]++; return 1; } return maxx; } void init() { int i; for(i=0;i<maxn;i++) { mark[i]=0; dp[i]=0; dig[i]=0; } } int main() { int n; int i,j,k; int num[maxn]; int m; int tot; while(scanf("%d",&n)!=-1) { init(); m=0; for(i=1;i<=n;i++) { scanf("%d",&num[i]); mark[num[i]]=i; } for(i=1;i<=n;i++) { tot=find(num[i]); dp[i]=tot; m=max(m,dp[i]); } printf("%d\n",m); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。