Luogu p5194 [usaco05dec]scales s solution

Luogu P5194 [USACO05DEC]Scales S Answer key

Topic link ：P5194 [USACO05DEC]Scales S

The question ：

John has a scale for weighing cows . What goes with it is $N$ ( $1\le N\le 1000$ ) A weight of known mass （ The mass values of all weights are 32 Bit signed integer range ）.

Every time you weigh a cow , He put a cow on one side of the scale , Then add weights to the other side of the balance , Until the balance is balanced , So the total mass of the weight at this time is the mass of the cow （ John can't put the weight on the side of the cow , Because cows don't like weighing , Whenever John puts the weight under her hoof , She would try to kick the weight in John's face ）.

The mass of the object that the balance can bear is not infinite , When the mass of an object on one side of the balance is greater than $C$ ( $1\le C\le 2^{30}$ ) when , The balance will be damaged . The weights are lined up according to their mass . also , In this line, from 3 Start with a weight , The mass of each weight is at least equal to the first two weights （ That is, the two weights with the largest mass among the weights with smaller mass ） The sum of the quality of .

John wants to know , With these weights and this balance he has , What is the maximum mass that can be weighed . Because the maximum bearing capacity of the balance is $C$ , He can't put all the weights on the balance .

Now John tells you the mass of each weight , And the maximum mass that the balance can bear , Your task is to choose some weights , Make their mass and the largest of all combinations without crushing the balance .

Obviously, the search was violent + prune

We can reverse search , That is, choose the big one first

It is not difficult to find that this is more likely to produce a larger answer

And then mess around

Code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(55)

int sum[N],mx,a[N],n,c;
void dfs(int now,int u)
{
    
    if(u<1)
    {
    
        mx=max(mx,now);
        return;
    }
    if(now+sum[u]<=mx) return;
    if(now+a[u]<=c)dfs(now+a[u],u-1);
    dfs(now,u-1);
    
}
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> c;
    for(int i=1; i<=n; i++)
    {
    
        cin >> a[i];
        if(a[i]>c){
    n=i-1;break;}
        sum[i]=sum[i-1]+a[i];
    }
    dfs(0,n);
    cout << mx << '\n';
    return 0;
}

Reprint please explain the source