問題
http://yukicoder.me/problems/no/390
N個の集合 S={x1,x2,...,xN} がある。
以下の条件を満たす「良い」数列の中で最も長い数列の長さは?
数列を (a1,a2,...,aM) とする
1. ∀i(1 <= i <= M) ai ∈ S
2. ∀i(1 <= i <= M - 1) 「ai < ai+1」かつ「ai+1はaiの倍数」
1 <= N <= 10^5
1 <= xi <= 10^6
xi != xj (1 <= i < j <= N)
考察
1. 組合せ問題の解き方は色々あるが…
2. 数学的に解く -> 倍数チェックがあるのでダメかも
3. DPで解く -> 解けそうかな…??
4. そもそも求めたい数列が最長増加部分列みたいな雰囲気あるから、DPで考えてみる
5. xiの数が微妙に小さいぞ???
6. xiの数は全て異なるぞ???
7. xiの数を要素に持ってDPを考えてみよう
い け る や ん
8. まず集合をソートしておく(ソートできるものは全てソートすると解法が分かったりする)
9. 以下のようにdpを計算する
dp[10^6+1]
dp[i]=(集合Sに含まれる1~iの数を使って作れる良い数列の中で最も長い数列の長さ)
xiの約数を {d1,d2,...,dn-1,dn=xi} とする
dp[xi] = max(dp[d1], dp[d2], ... , dp[dn-1])
10. ぶっちゃけ計算量計算できないんですけど、間に合いそうな感じある
実装
http://yukicoder.me/submissions/102232
int N; int x[101010]; //----------------------------------------------------------------- typedef long long ll; vector<ll> enumdiv(ll n) { vector<ll> S; for (ll i = 1; i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); } sort(S.begin(), S.end()); return S; } //----------------------------------------------------------------- int dp[1010101]; int main() { scanf("%d", &N); rep(i, 0, N) scanf("%d", &x[i]); sort(x, x + N); rep(i, 0, N) dp[x[i]] = 1; rep(i, 1, 1000001) if(dp[i]){ auto v = enumdiv(i); for (int j : v) if(j != i) dp[i] = max(dp[i], dp[j] + 1); } int ans = 0; rep(i, 0, N) ans = max(ans, dp[x[i]]); cout << ans << endl; }