链接
https://codeforces.com/contest/1475/problem/G
题意
长度为 $n$ 的数组 $a$，删去一些数使数组内任意两个数的较大值为较小值的倍数，求最少删去多少数。
思路
记 $tot_i$ 为 $i$ 在数组 $a$ 中的个数，
将数组 $a$ 排序去重后，
记 $dp_i$ 为以第 $i$ 大的数为最大数的满足要求的数组的长度：
$dp_i=\max(dp_j+tot_{a_i})(a_j \mid a_i)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=2e5+5;
int a[N],dp[N],tot[N],pos[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
VI a(n);
memset(tot,0,sizeof tot);
memset(pos,-1,sizeof pos);
for(int i=0;i<n;i++) cin>>a[i],++tot[a[i]];
sort(ALL(a));
a.resize(unique(ALL(a))-a.begin());
for(int i=0;i<SZ(a);i++) pos[a[i]]=i;
for(int i=0;i<SZ(a);i++) dp[i]=0;
for(int i=0;i<SZ(a);i++) {
int t=0;
for(int j=1;j*j<=a[i];j++)
if(a[i]%j==0) {
if(pos[j]!=-1) t=max(t,dp[pos[j]]+tot[a[i]]);
if(pos[a[i]/j]!=-1) t=max(t,dp[pos[a[i]/j]]+tot[a[i]]);
}
dp[i]=t;
}
int mx=0;
for(int i=0;i<SZ(a);i++) mx=max(mx,dp[i]);
cout<<n-mx<<'\n';
}
return 0;
}
|