yukicoder No390
解説
基本的な解法の方針は動的計画法です dp[i] := 値iの要素が右端になる時の長さの最大値 とします。そうすると以下のような漸化式を立てることができます。 dp[i] = dp[y]+1 (yはiの約数) 基本的にはこれだけなのであとは値iの約数を列挙しなければいけません. √xの値までを調べ、x%i== 0の時、iは約数であり、n/iも約数になります。
コード
#include <iostream> #include <algorithm> #include <vector> using namespace std; vector<int> divisor(int n){ vector<int> res; for(int i=1; i*i<=n; i++){ if(n%i == 0){ res.push_back(i); if(i != 1 && i != (n/i)){ res.push_back(n/i); } } } return res; } int main(void){ int n, a[100005]; cin >> n; for(int i=0; i<n; i++){ cin >> a[i]; } sort(a, a+n); int dp[1000006]; fill(dp, dp+1000006, 0); int m = 1; dp[a[0]] = 1; for(int i=1; i<n; i++){ dp[a[i]] = 1; if(a[i] != 1){ vector<int> res = divisor(a[i]); for(int j=0; j<res.size(); j++){ dp[a[i]] = max(dp[a[i]], dp[res[j]]+1); m = max(m, dp[a[i]]); } } } cout << m << endl; return 0; }