P4411BZOJ1978 [BJWC2010]取数游戏(动态规划dp)

P4411

---

一道dp

---

f[i]表示一定选第i个数的条件下前i个数所能得到的最优值

last[i]表示质因数i在数列a中最后出现时的下标

状态转移方程为\(f[i]=max\{f[last[j]\:|\: j|i \}+1\)

复杂度\(O(n\sqrt{a_i})\)

---

#include <bits/stdc++.h>
using namespace std;
int n,l,ans,a[50005],last[1000005],f[50005];
signed main(){scanf("%d%d",&n,&l);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){int SQRT=sqrt(a[i]); //循环外先算出，提高效率for(int j=1;j<=SQRT;j++)if(a[i]%j==0){int x=j,y=a[i]/j; //x,y是a[i]的一组因数if(x>=l) f[i]=max(f[i],f[last[x]]+1); //由上一个有相同质因数的数转移得到if(y>=l) f[i]=max(f[i],f[last[y]]+1);last[x]=last[y]=i; //修改质因数的最后出现下标}ans=max(ans,f[i]); //保存最优解}printf("%d",ans);
}