首页 > 代码库 > BZOJ 1978 取数游戏（DP）
BZOJ 1978 取数游戏（DP）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1978
题意：给出一个数列a，在其中找出下标依次增大的数，使得任意相邻的两个数的最大公约数大于等于m。找出最多的数字。
思路：f[i]表示前面的数字中最大公约数为i可以找出的最多的数字个数。那么对于当前数字x：
接着更新f：
int f[N],a[N];int n,m;int main(){ RD(n,m); int i; FOR1(i,n) RD(a[i]); int j,k; FOR1(i,n) { k=0; for(j=1;j*j<=a[i];j++) if(a[i]%j==0) { k=max(k,f[j]); k=max(k,f[a[i]/j]); } k++; for(j=1;j*j<=a[i];j++) if(a[i]%j==0) { if(j>=m) f[j]=k; if(a[i]/j>=m) f[a[i]/j]=k; } } int ans=0; for(i=m;i<N;i++) ans=max(ans,f[i]); PR(ans);}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。