洛谷5194 [USACO05DEC]Scales

题意

给出 $N$ 个砝码，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中质量最大的两个）的质量的和，求能凑出的 $\le C$ 的重量最大值。

$N\le 1000,C\le 2^{30}$ 。

题解

每个砝码的质量至少等于前面两个砝码的质量的和

所以 $N\le 30$ 。。。

所以爆搜就行了，拿个前缀和优化剪枝，如果剩下的都能取就直接取完。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,ans,s[35],sum[35];

void dfs(ll x,ll cur)
{
    if (cur>m) return;
    if (cur+sum[x-1]<=m) return (void)(ans=max(ans,cur+sum[x-1]));
    ans=max(ans,cur);
    for (ll i=1;i<x;i++) dfs(i,cur+s[i]);
}

signed main()
{
    n=read(); m=read();
    for (ll i=1;i<=n;i++) sum[i]=sum[i-1]+(s[i]=read());
    dfs(n+1,0);
    return !printf("%lld",ans);
}