题目链接
https://www.luogu.org/problem/P1463
继续阅读[洛谷 1463][POI2002][HAOI2007]反素数一份咕咕了两个月的题解?(其实有两道题的题解都在洛谷上发布了)
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; }
在某位 dalao 的建议下,第一轮 Div.3 比赛总算是顺利举行了(然而开始几分钟服务器却炸了)。
http://codeforces.com/contest/977
继续阅读[CF977X]Codeforces Round #479 (Div. 3)