暴力 \(DP\)
先考虑暴力 \(DP\) 该怎么写.
因为每个序列之后是否能加上新的节点只与其结尾有关, 因此我们设 \(f_i\) 为以 \(i\) 为结尾的最长序列长度.
每次枚举一个前置状态, 判断是否合法之后进行转移.
优化 \(DP\)
上面做法的瓶颈在于, 判断是否合法需要大量时间.
则有一个比较巧妙的做法.
首先对于每一个数 \(a_i\),\(\sqrt {max_{x=1}^na_x}\) 范围内的某一质数 \(j\), 我们求出 \(p_{i,j}\) 表示 \(a_i\) 是否含有质因数 \(j\).
然后, 再对与每一个数 \(a_i\), 我们用 \(s_i\) 存下其大于 \(\sqrt{max_{x=1}^na_x}\) 的质因数, 若没有则 \(s_i=1\).
那么, 我们可以用 \(g_x\) 表示所有的 \(a_i\) 含有质因数 \(x\) 的 \(f_i\) 的最大值, 用 \(Mx_x\) 表示所有的 \(s_i=x\) 的 \(f_i\) 的最大值 \((x!=1)\), 然后记下 \(MP\) 和 \(MP\_\) 分别表示 \(Mx_x\) 的最大值和次大值所对应的 \(x\).
转移时我们可以从所有当前 \(a_i\) 不含的质数所对应的 \(g\) 转移, 然后若 \(s_i=MP\), 则从 \(Mx_{MP\_}\) 转移, 否则从 \(Mx_{MP}\) 转移.
具体实现时我们可以把 \(g_x\) 中 \(x\) 的定义改为第 \(x\) 个质数.
代码
- #include<bits/stdc++.h>
- #define Tp template<typename Ty>
- #define Ts template<typename Ty,typename... Ar>
- #define Reg register
- #define RI Reg int
- #define Con const
- #define CI Con int&
- #define I inline
- #define W while
- #define N 100000
- #define M 1000000
- #define SM 1000
- #define Gmax(x,y) (x<(y)&&(x=(y)))
- using namespace std;
- int n,a[N+5];
- class FastIO
- {
- private:
- #define FS 100000
- #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
- #define tn (x<<3)+(x<<1)
- #define D isdigit(c=tc())
- char c,*A,*B,FI[FS];
- public:
- I FastIO() {A=B=FI;}
- Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
- Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
- }F;
- template<int SZ> class LinearSiever// 线性筛筛质数
- {
- public:
- int Pt,P[SZ+5];
- I LinearSiever()
- {
- RI i,j;for(i=2;i<=SZ;++i) for(!P[i]&&(P[++Pt]=i),
- j=1;j<=Pt&&1LL*i*P[j]<=SZ;++j) if(P[i*P[j]]=1,!(i%P[j])) break;
- }
- };
- class PrimeSolver
- {
- private:
- int f[N+5],g[SM+5],Mx[M+5],s[N+5],p[N+5][SM+5];LinearSiever<SM> P;
- I void Init(CI x)// 初始化, 质因数分解预处理每个数
- {
- RI i;for(s[x]=a[x],i=1;i<=P.Pt;++i)
- {
- if(s[x]%P.P[i]) continue;p[x][i]=1;
- W(!(s[x]%P.P[i])) s[x]/=P.P[i];
- }
- }
- public:
- I void Solve()
- {
- RI i,j,MP=0,MP_=0,ans=0;for(i=1;i<=n;++i)//DP
- {
- for(Init(i),f[i]=0,j=1;j<=P.Pt;++j) !p[i][j]&&Gmax(f[i],g[j]+1);// 从当前 a[i] 不含的质数转移
- MP^s[i]?Gmax(f[i],Mx[MP]+1):Gmax(f[i],Mx[MP_]+1);// 从 Mx 处转移
- for(j=1;j<=P.Pt;++j) p[i][j]&&Gmax(g[j],f[i]);if(s[i]==1||f[i]<=Mx[s[i]]) continue;// 更新 g 值
- Mx[s[i]]=f[i],MP^s[i]&&(Mx[MP]<f[i]?(MP_=MP,MP=s[i]):Mx[MP_]<f[i]&&(MP_=s[i]));// 更新 Mx 值, 并更新 MP 和 MP_
- }
- for(i=1;i<=n;++i) Gmax(ans,f[i]);printf("%d",ans);// 统计并输出答案
- }
- }S;
- int main()
- {
- freopen("demon.in","r",stdin),freopen("demon.out","w",stdout);
- RI i;for(F.read(n),i=1;i<=n;++i) F.read(a[i]);return S.Solve(),0;
- }
来源: http://www.bubuko.com/infodetail-3136329.html