题外话

这题看起来很像贪心啊，但由于本人贪心太废了，所以只好使用二分加动态规划来做了。

思路

先把相同的数缩成一个数，将原本长度为

n

的

a

数组变为长度为

m

的互不相同的

a

数组，用

b_i

记录

i

的出现次数。观察到答案具有单调性，考虑二分答案

x

。问题关键在于如何判断划分出的集合数量能不能为

x

。我们枚举每一个

a_i

，用

dp_{i,j}

表示前

i

个数，能不能划分出

j

个大小为奇数的集合，若能

dp_{i,j}

为

1

，否则为

0

。则最后

dp_{m,0}

就是答案。

考虑转移，对于

dp_{i,j}

，我们枚举

k

表示使用了

k

个

a_i

放入了之前的

k

个大小为奇数的集合，剩余的

(b_{a_i}-k)

个

a_i

放入了之前的

(b_{a_i}-k)

个大小为偶数的集合，其余集合的奇偶性不变。既然放一个数字集合奇偶性会取反，那么

dp_{i,j}

就是可以从

dp_{i-1,j+2\times k-b_{a{i}}}

转移过来的，取最大值即可。

求出最小值后我们还要构造一种方案，此时只需要用

f_{i,j}

记录

dp_{i,j}

是从哪里转移过来的即可。

由于循环前两维总和为

n

，总时间复杂度

O(n^2\log n)

。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,a[1005],b[1000005],c[1005],dp[1005][1005],f[1005][1005];
vector<int> v[1005];
bool check(int x) {
	memset(dp,0,sizeof(dp));
	dp[1][b[a[1]]]=1;
	for(int i=2; i<=m; i++) {
		if(b[a[i]]>x)return 0;
		for(int j=0; j<=x; j++) {
			for(int k=0; k<=b[a[i]]; k++) {
				if(j+k-b[a[i]]>=0&&x-j-k>=0)dp[i][j]=max(dp[i][j],dp[i-1][j+2*k-b[a[i]]]);
			}
		}
	}
	return dp[m][0];
}
bool cmp(vector<int> x,vector<int> y){
	return x.size()%2>y.size()%2;
}
void gx(int x) {
	memset(dp,0,sizeof(dp));
	dp[1][b[a[1]]]=1;
	f[1][b[a[1]]]=0;
	for(int i=2; i<=m; i++) {
		for(int j=0; j<=x; j++) {
			for(int k=0; k<=b[a[i]]; k++) {
				if(j+k-b[a[i]]>=0&&x-j-k>=0) {
					if(dp[i-1][j+2*k-b[a[i]]]) {
						dp[i][j]=1;
						f[i][j]=k;
						break;
					}
				}
			}
		}
	}
	int j=0;
	for(int i=m; i>=1; i--) {
		c[i]=f[i][j];
		j+=2*f[i][j]-b[a[i]];
	}
	for(int i=1; i<=m; i++) {
		int y=1;
		for(int j=1; j<=b[a[i]]; j++) {
			if(v[y].size()%2==1) {
				if(c[i]) {
					c[i]--;
					v[y].push_back(a[i]),y++;
				}
				else{
					while(v[y].size()%2==1)y++;
					v[y].push_back(a[i]),y++;
				}
			} else v[y].push_back(a[i]),y++;
		}
		sort(v+1,v+x+1,cmp);
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--) {
		cin>>n;
		for(int i=1; i<=n; i++)cin>>a[i];
		if(n%2==1) {
			cout<<-1<<"\n";
			continue;
		}
		for(int i=1; i<=n; i++)b[a[i]]++;
		sort(a+1,a+n+1);
		m=unique(a+1,a+n+1)-a-1;
		int l=1,r=n/2,mid,ans=-1;
		while(l<=r) {
			mid=(l+r)/2;
			if(check(mid))ans=mid,r=mid-1;
			else l=mid+1;
		}
		cout<<ans<<"\n";
		if(ans!=-1) {
			gx(ans);
			for(int i=1; i<=ans; i++) {
                cout<<v[i].size()<<" ";
                for(int j=0;j<v[i].size();j++){
                	cout<<v[i][j]<<" ";
				}
				v[i].clear();
				cout<<"\n";
			}
		}
		for(int i=1; i<=m; i++)b[a[i]]=0;
	}
	return 0;
}

后记

贪心我们分手吧，我怕动态规划误会。

题解：P13494 【MX-X14-T4】分门别类

文章操作

题外话

思路

代码

后记

相关推荐

评论

题解：P13494 【MX-X14-T4】分门别类