Codeforces 1077E （二分乱搞或者dp）

题意：给你一个数组，可以从中选区若干种元素，但每种元素选区的个数前一种必须是后一种的2倍，选区的任意2种元素不能相同，问可以选取最多的元素个数是多少？

思路1(乱搞）：记录一下每种元素的个数，然后暴力枚举最少的元素个数，计算符合题意的最优情况。

代码：

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<map>

#include<set>

#include<bitset>

#include<vector>

#include<iostream>

#define INF 0x3f3f3f3f

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pb push_back

using namespace std;

const int maxn=1000010;

map<int,int> mp;

map<int,int>::iterator it;

int a[maxn],b[maxn],cnt;

int v[maxn];

int main(){

	int n,ans=0;

//	freopen("in.txt","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		mp[a[i]]++;

	}

	for(it=mp.begin();it!=mp.end();it++){

		b[++cnt]=it->second;

	}

	sort(b+1,b+1+cnt);

	for(int i=1;i<=b[cnt];i++){

		int now=0,sum=i;

		while(now<=n){

			int pos=lower_bound(b+1,b+1+cnt,sum)-b;

			while(pos<=cnt&&v[pos]==i)pos++;

			v[pos]=i;

			if(pos>cnt)break;

			now+=sum;

			sum=sum+sum;

		}

		ans=max(ans,now);

	}

	printf("%d\n",ans);

}

　思路2：DP 设dp[i]为最少元素个数为i时的最优解，将元素的个数从小到大排序后，从后往前更新答案。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=200010;

int dp[maxn*2];

map<int,int> mp;

int a[maxn];

int main(){

	int n,ans=0,cnt=0;

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

		mp[a[i]]++;

	}

	for(auto i:mp){

		a[++cnt]=i.second;

	}

	sort(a+1,a+1+cnt);

	for(int i=cnt;i>=1;i--)

		for(int j=1;j<=a[i];j++){

			dp[j]=max(dp[j],j+dp[j*2]);

			ans=max(ans,dp[j]);

		}

	printf("%d\n",ans);

}

巴特西

Codeforces 1077E （二分乱搞或者dp）

最新文章

热门文章