Codeforces Round＃522 Div2E(思维，背包，组合数学)

#include<bits/stdc++.h>
using namespace std;
int a[107];
int b[10007][107];
int c[107][107];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
　　scanf("%d",&a[i]);
}
b[0][0]=1;
for(int i=1;i<=n;i++){//遍历１到ｎ
　　for(int j=i;j>=1;j--){
　　　　for(int k=10000;k>=a[i];k--){
　　　　　　b[k][j]=b[k][j]+b[k-a[i]][j-1];//ｋ为重量，ｊ为重物的个数，ｋ-a[i]遍历了所有情况
　　　　}
　　}
}
for(int i=0;i<=n;i++)
　　c[i][0]=1,c[i][i]=1;//排列组合Ｃ
for(int i=1;i<=n;i++){
　　for(int j=1;j<=i-1;j++){
　　　　c[i][j]=c[i-1][j-1]+c[i-1][j];
　　}
}
sort(a+1,a+1+n);
int ans=0;
int num=0;
for(int i=1;i<=n;i++){
　　num++;
　　int cnt=i;
　　while(1){
　　　　if(a[cnt+1]==a[i])
　　　　　　cnt++;
　　　　else
　　　　　　break;
　　}　　
　　for(int j=i;j<=cnt;j++){
　　　　if(c[cnt-i+1][j-i+1]==b[(j-i+1)*a[i]][j-i+1])//ｂ是所有重物组合起来的情况，ｊ及重量和，ｃ是相等重量重物组合起来的情　　况，如果相等，则说明如此重量只能通过相等重物来组合，即惟一
　　　　ans=max(ans,j-i+1);
　　}
　　i=cnt;
}
if(num==2)//特判补集情况
　　printf("%d",n);
else
　　printf("%d",ans);
return 0;
}

巴特西

Codeforces Round＃522 Div2E(思维，背包，组合数学)

最新文章

热门文章