博客

Problem – G – Codeforces

题意：

有n个数，要你挑选最大的子集，使得对于集合中两个不同的数x,y，有 x|y 或 y|x

思路：

考虑dp

状态设计：设dp[i]表示 i 作为集合中最小值的最大集合size

既然 i 作为最小值，肯定由它的倍数转移过来

因此我们去枚举倍数

就，我们先去倒序枚举因子，再去正序枚举倍数

对于因子 i ，我们先去枚举其倍数，并统计倍数的dp值的最大值

统计完后，因子 i 就由这个dp最大值的倍数转移过来，这里很像LIS

Code：

#include <bits/stdc++.h>
using namespace std;
#define low(x) (x&-x)
#define mnf 0x3f3f3f3f
#define inf 0xc0c0c0c0
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define pre(i,x,y) for(int i=y;i>=x;i--)
//#define int long long
const int mxn=1e6+10,mxv=1e6+10;
int n;
int a[mxn],dp[mxn],mp[mxn];
void solve(){
    memset(mp,0,sizeof(mp));
    memset(dp,0,sizeof(dp));
    cin>>n;
    rep(i,1,n) cin>>a[i],mp[a[i]]++;
    for(int i=2e5;i>=1;i--){
        int mx=0;
        for(int j=i;j<=2e5;j+=i){
            mx=max(mx,dp[j]);
        }
        dp[i]=mx+mp[i];
    }
    cout<<n-*max_element(dp+1,dp+1+n)<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

总结：

如果这道题定义的状态是集合中最大的数所属集合的最大集合size，那么每次枚举数的时候都要去枚举其约数，然后从约数转移过来，这样O(n根号n)显然超时，因此我们考虑枚举倍数

枚举倍数的话，就必须从倍数转移过来，这样就要倒序枚举因子，正序枚举倍数，这样是O(nlogn)的

状态转移比较麻烦时，可以转变一下状态的定义