Codeforces-1475G Strange Beauty


Problem

Portal


Meaning

给定一个数组,问最少删去几个数组中的元素,使得数组中剩下的元素两两之间,大数是小数的倍数。


Accepted Code $O(NlogN)$

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N = 2e5+10;

int a[N], dp[N];

signed main()
{
    int T; cin >> T;
    while(T -- )
    {
        memset(dp, 0, sizeof dp);
        int n, ans = 0; cin >> n;
        unordered_map<int, int> ump;
        for(int i = 1 ; i <= n ; i ++ )
        {
            cin >> a[i];
            ump[a[i]] ++ ;
        }
        for(int i = 1 ; i < N ; i ++ )
        {
            dp[i] += ump[i];
            for(int j = i*2 ; j < N ; j += i) dp[j] = max(dp[i], dp[j]);
            ans = max(ans, dp[i]);
        }
        cout << n-ans << endl;
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Codeforces-1485A Add and Divide Codeforces-1485A Add and Divide
ProblemPortal Thoughts b加1次1,那么后面的除法操作必然少>=1次,总操作次数必然减小。 我们思考最后答案最多为$log_2^{1e9}+1=30$次($a=1e9, b=1$),那么也就是说我们加法操作最多
Next 
Codeforces-1475F Unusual Matrix Codeforces-1475F Unusual Matrix
ProblemPortal Thoughts Accepted Code#include <bits/stdc++.h> #define int long long using namespace std; const int
  TOC