P13341 题解

建议降蓝。

考虑如下构造：任取

12

的约数

k

，以及

d\ge \frac{12}{k}

。找出

k\cdot d

个数，每

k

个数分一段，一共

d

段。然后找出

\binom{d}{\frac{12}{k}}

个人，每个人从中选出

\frac{12}{k}

段，这样不重不漏地覆盖所有可能的选择情况。

例如当

k=4,d=5

时，找出五个段

[0,3],[4,7],[8,11],[12,15],[16,19]

，每个人从中选出

3

段，一共十种选择，对应十个人。

容易证明这种构造满足条件。并且我们可以把多个这样的结构拼在一起——只需要保证它们使用的数互不相同即可。

找出所有可能的构造，使用动态规划把它们组合在一起即可。

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=100;
int n,C[N][N],f[N],g[N],d[N],x[N],cnt[N],a[N];
void dfs(int A,int B,int k,int dif){
	if (A<B||B<0){
		return;
	}
	if (A==0){
		for (int i=1;i<=(12/k);++i){
			for (int j=0;j<k;++j){
				cout<<dif+a[i]*k+j<<' ';
			}
		}
		cout<<endl;
		return;
	}
	dfs(A-1,B,k,dif);
	a[B]=A-1;
	dfs(A-1,B-1,k,dif);
}
void solve(int n,int dif){
	if (n==0){
		return;
	}
//	cout<<"solve "<<n<<' '<<g[n]<<endl;
	int c=g[n];
	dfs(cnt[c],12/x[c],x[c],dif);
	solve(n-c,dif+d[c]);
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	for (int i=0;i<N;++i){
		for (int j=C[i][0]=1;j<=i;++j){
			C[i][j]=min(C[i-1][j]+C[i-1][j-1],N);
		}
	}
	cnt[1]=1;d[1]=12;x[1]=12;
	for (int k=1;k<12;++k){
		if (12%k){
			continue;
		}
		for (int o=12/k+1;o*k<=50;++o){
			int c=C[o][12/k];
			if (c>50){
				break;
			}
			if (d[c]==0||d[c]>o*k){
				d[c]=o*k;x[c]=k;cnt[c]=o;
			}
		}
	}
	for (int i=1;i<=50;++i){
		f[i]=51;
	}
	for (int i=0;i<=50;++i){
//		cout<<f[i]<<endl;
		for (int j=1;i+j<=50;++j){
			if (!d[j]){
				continue;
			}
			if (f[i]+d[j]<f[i+j]){
				f[i+j]=f[i]+d[j];
				g[i+j]=j;
			}
		}
	}
	cin>>n;
	solve(n,0);
	return 0;
}

文章操作

相关推荐

评论

P13341 题解