# 银河美术馆-Beautyyu

Beautyyu言醴的个人独立博客

0%

# 一种基于数值的dp遍历方法 Codeforces1475G Strange Beauty|题解

Let’s calculate for each number $x$ how many times it occurs in the array $a$. Let’s denote this number as $cnt[x]$.

Let’s use the dynamic programming method. Let $dp(x)$ be equal to the maximum number of numbers not greater than $x$ such that for each pair of them one of the conditions above is satisfied. More formally, if $dp(x)=k$, then there exists numbers $b_1,b_2,…,b_k (b_i\leq x)$ from the array $a$ such that for all $1 \leq i, j \leq k$ one of the conditions above is satisfied.

Then to calculate $dp(x)$ you can use the following formula:

$dp(x) = cnt(x) + \max \limits_{y = 1,\ x\ mod\ y = 0}^{x-1} dp(y)$

Note that to calculate $dp(x)$ you need to go through the list of divisors of $x$. For this, we use the sieve of Eratosthenes.

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
LL T;
LL n, arr[300000], cnt[300000], dp[300000];
int main (){
cin >> T;
while (T--){
scanf("%lld", &n);
for (LL i = 1; i <= 200000; ++ i)
cnt[i] = 0;
for (LL i = 1; i <= n; ++ i){
scanf("%lld", &arr[i]);
cnt[arr[i]] ++;
}
for (LL i = 1; i <= 200000; ++ i)
dp[i] = cnt[i];
sort(arr + 1, arr + 1 + n);
LL m = unique(arr + 1, arr + 1 + n) - arr - 1;
for (LL k = 1;k <= m; ++ k){
LL i = arr[k];
for (LL j = i * 2; j <= 200000; j += i){
dp[j] = max(dp[j], dp[i] + cnt[j]);
}
}
printf("%lld\n", n - *max_element(dp + 1, dp + 200001));
}
return 0;
}