VK Cup 2015 - Finals, online mirror F. Clique in the Divisibility Graph
"As you must know," 怖い…
練習です。
解法
dp[n] = (nを約数とする数字の個数)とします。数列 a を直接使うのではなく, b[p] = (数列 a の中に p という数がいくつあるか)という配列を用意しておけば, dp[n] の計算は, MAXN/n で処理することが出来ます(MAXN は数列 a に入る最大の数)。
これはだいたい になるので時間内に間に合います。
const int MAXN = 1000001; int a[MAXN]; int b[MAXN]; int dp[MAXN]; int n; int dfs(int cur) { if (b[cur] == 0) return 0; int& ret = dp[cur]; if (ret > 0) return ret; ret = 0; for (int i = 2; i*cur < MAXN; i++) { ret = max(ret, dfs(i*cur)); } ret += b[cur]; return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; b[a[i]]++; } int ans = 0; for (int i = 1; i < MAXN; i++) { if (dp[i] == 0) ans = max(ans, dfs(i)); } cout << ans << endl; return 0; }