P5194 Scales S——dfs(前缀和剪枝)

本文主要是介绍P5194 Scales S——dfs(前缀和剪枝)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门https://www.luogu.com.cn/problem/P5194手切第一遍，没想到可以用前缀和剪枝，并且是从小到大搜了，不出意外40分TLE+WA

第二遍：代码及思路

// Problem: 
//     P5194 [USACO05DEC] Scales S
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5194
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
using namespace std;
#define int long long
int n,m;
const int N=1005;//这里其实的1000范围是骗人的，要敏感题目里有个斐波那契数列（n+2 = n+1  +  n）
//实际上50以内就能包住，于是这里考虑dfs一下
int a[N];
int b[N];//前缀和优化
int maxn=0;void dfs(int x,int num){if(b[x]+num<=maxn) return;//如果前缀和+当前的还没maxn大，就不用搜了
//我想，这里之所以使用前缀和，是因为从大到小搜，前面的部分与后方差距大，对值其实影响不大，这时候用一个前缀和就可以省去很多麻烦maxn=max(maxn,num);for(int i=x;i>=1;--i){if(num+a[i]<=m)//一定要判断小于m才能搜，这里应该也算是一个剪枝，因为我尝试把这个放在上面判断通过不了dfs(i-1,num+a[i]);//i-1意思是本层的事情本层解决，直接进入下一层，注意这里是i//这里看似没有不取的情况，实际上因为用了for，所以是这一次取一种，效果一样}如果不用for也可以考虑进行以下操作，当然我不知道为什么这么搞不判第0层截至也能AC（迷惑）//dfs(cur+fama[index],index-1);//dfs(cur,index-1);
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;++i){cin>>a[i];if(a[i]>m){n=i-1;break;}b[i]=b[i-1]+a[i];}dfs(n,0);//从大往小取，能减少很多递归层数cout<<maxn;return 0;
}

如下

这篇关于P5194 Scales S——dfs(前缀和剪枝)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---