题目链接:http://codeforces.com/problemset/problem/264/B
代码:
#include<cstdio> #include<iostream> #include<vector> #include<cstring> using namespace std; const int maxn = 105000; int dp[maxn]; vector<int> dx[maxn]; void get_div() //筛因子 { for(int i=2; i<maxn; i++) for(int j=i; j<maxn; j+=i) dx[j].push_back(i); } int main() { freopen("E:\acm\input.txt","r",stdin); int n; get_div(); while(cin>>n) { memset(dp,0,sizeof(dp)); for(int i=1; i<=n; i++) { int a; cin>>a; int Max = 1; for(int j=0,sz=dx[a].size(); j<sz; j++) Max = max(Max,dp[ dx[a][j] ] + 1); //求出第i个数因子中传递的最大的链 for(int j=0,sz=dx[a].size(); j<sz; j++) dp[ dx[a][j] ] = max(Max,dp[ dx[a][j] ]); //更新操作 } int ans = 1; //这里要注意 for(int i=1; i<maxn; i++) ans = max(ans,dp[i]); cout<<ans<<endl; } return 0; } //这个题关键在 因子 上面