分类： 搜索

一份咕咕了两个月的题解？（其实有两道题的题解都在洛谷上发布了）

继续阅读USACO 2018 December Silver

题目链接

https://www.luogu.org/problem/P5194

题解

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

虽然题目中说 \(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;
}