76分求助
查看原帖
76分求助
504384
FE自动机楼主2021/10/11 13:52

为啥76分

#include<bits/stdc++.h>
using namespace std;
int a[105],used[105],n,len,m,minn,sum;
bool cmp(const int &a,const int &b)
{
    return a>b;
}
void dfs(int k,int last,int rest)
{
    if(k==m){cout<<len<<endl;exit(0);}
    if(rest==0)
        for(int i=1;i<=n;++i)
            if(!used[i]){used[i]=1;dfs(k+1,i,len-a[i]);break;}
    for(int i=last+1;i<=n;++i)
    {
        if(!used[i]&&rest>=a[i])
        {
            used[i]=1;
            dfs(k,i,rest-a[i]);
            used[i]=0;
            int j=i;
            while(i<n&&a[i]==a[j])++i;
            if(i==n)return;
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        if(a[i]>50)
        {
            --i,--n;
            continue;
        }
        minn=max(minn,a[i]);
        sum+=a[i];
    }
    stable_sort(a+1,a+n+1,cmp);
    for(int i=minn;i<=sum;++i)
    {
        if(sum%i==0)
        {
            memset(used,0,sizeof used);
            len=i;
            used[1]=1;
            m=sum/i;
            dfs(1,1,len-a[1]);
        }
    }
    return 0;
}
2021/10/11 13:52
加载中...