Problem - 1475G - G. Strange Beauty(调和级数+dp)

题目大意:对于一个序列,如果对于任意的$i,j(i?=j)$都满足$gcd(a_i,a_i)=min(a_i,a_j)$,那么就称该序列为有效序列.你现在可以删除给定序列中的一些元素,求最少删除多少元素,可以使得整个序列变为有效序列.

解题思路:我们首先考虑一下如何得到一个有效序列,枚举$a_i$进行因式分解,然后再对其分解后的因子再因式分解,这样复杂度很显然是不可行的,那我们正向思考一下,对于每个$a_i$,它所能产生的贡献一定是对应$k?a_i$,枚举$a_i$,经过调和级数优化后复杂度就降到了$O(nlo{g}_n)$.定义$dp[i]$的含义是当前序列中最大数是$i$时序列中的元素个数.$dp[i?k]=dp[i]+num[i?k]$.

#include<bits/stdc++.h>
using namespace std;
int xxxxxxxx;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int N = 2e5+5;
int num[N], dp[N];
void solve(){
    int n;cin>>n;int tem;int m =0 ;memset(num, 0, sizeof num);memset(dp, 0, sizeof dp);for (int i = 1; i <= n; ++i){
    cin>>tem;m=max(m, tem);num[tem]++;}for (int i = 1; i <= m; ++i){
    dp[i]=num[i];}for (int i = 1; i <= m; ++i){
    for (int j = 2; j * i <= m; ++j){
    dp[i*j]=max(dp[i*j], dp[i]+num[i*j]);}}int maxd = 0;for (int i = 1; i <= m; ++i)maxd=max(maxd, dp[i]);cout << n-maxd << "\n";
}int main(){
    syncfalse#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endifint t;cin>>t;for (;t;--t){
    solve();}return 0;
}