CF264B Good Sequences

Solution

虽然每个题要求的最长序列的满足条件不一样，但是方法总是那一个——DP。

因为前后转移和 (gcd) 有关系，我们可以将 (gcd) 用因子的方式表示。

我们设 (dp_i) 表示以 (a_i) 结尾的最长序列， (f_i) 为所有含有 (i) 这个因子的 (a_x) 中的 (max{dp_x}) 。当方程转移到 (x) 位时，枚举 (a_x) 的因子，更新 (dp_x=maxlimits_{d|a_x,d ot=1}{f_d}+1) ，然后再将 (f_d) 更新，最后搞一个 (ans) 记录最大值就行了。

小细节：在更新 (f_d) 的时候，可以只更新质因子的 (f) ，因为在转移的时候，用非质因子更新答案，其实在枚举质因子的时候就已经更新过了，并且质因子的答案不会比非质因子差。而且 (dp) 数组也不需要，当枚举到某一位时，这一位以前的最大值已经求出，所以可以直接和 (ans) 更新。

代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;
const int N=100010;
int ans,n,a[N],f[N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

inline void solve(int x){
    int m=sqrt(x),sum=0;
    for(int i=2;i<=m;i++)
        if(x%i==0) sum=max(max(sum,f[i]),f[x/i]);
    sum=max(sum,f[x]);//记得x也算x的因数
    for(int i=2;i<=m;i++)
        if(x%i==0){
            f[i]=sum+1;
            while(x%i==0) x/=i;
        }
    f[x]=sum+1;
    ans=max(ans,sum+1);//不记录dp[] 直接更新
}

int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) solve(a[i]);
    printf("%d
",ans);
    return 0;
}