[洛谷 5194][USACO05DEC]Scales 天平

乍一看,感觉和装箱问题一样,但是仔细看一下数据范围,就知道背包的做法是不可行的。

虽然题目中说\(n \leq 1000\),但考虑到“每个砝码的质量至少等于前面两个砝码的质量的和”这一条件,可以推出\(n \leq 30\)。

在这么小的数据范围下,我们考虑用搜索的方法来解决这道题。

#include <iostream>
#include <algorithm>
using namespace std;
long long sum[1005],a[1005],ans,n,c;
void dfs(int cur,long long x)
{
 if(x>c)return;
 if(sum[cur-1]+x<=c)
 //一个剪枝:如果前面那些砝码可以全部取走,那直接取走即可。
 {
  ans=max(ans,sum[cur-1]+x);
  return;
 }
 ans=max(ans,x);
 for(int i=1;i<cur;i++)
  dfs(i,x+a[i]);
 return;
}
int main()
{
 cin>>n>>c;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i];
  sum[i]=sum[i-1]+a[i];
 }
 dfs(n+1,0);
 cout<<ans<<endl;
 return 0;
}