Processing math: 50%

[洛谷 5194][USACO05DEC]Scales 天平

题目链接

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

题解

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

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

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}