Codeforces Round #697 (Div. 3) G Strange Beauty

拼搏现实的明天。 2024-03-31 12:59 39阅读 0赞

[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)的**

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

[Problem - G - Codeforces]: https://codeforces.com/contest/1475/problem/G