P5194 [USACO05DEC]Scales S

思路

其实还是一知半解
用前缀和优化的DFS
先做个前缀和
然后每次找一个数，如果这个数前面所有的数加上这个数都可以取，就直接取
不行的话就在这个数的前面找数，然后判断能否全部取走，能取走就取走，然后得到最大值，然后最终是用不可以取走所有前面的情况下在从前面重新开始枚举。

还不太懂，但要是可以把这题搞懂，对搜索水平会有很大的提升！

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, c;
const int N = 10005;
int a[N], sum[N];
int ans = 0;void dfs(int cnt, int x)
{
    if (x > c){
    return;}if (sum[cnt - 1] + x <= c){
    ans = max(ans, sum[cnt - 1] + x);return;}ans = max(ans, x);for (int i = 1; i < cnt; i ++ ){
    dfs(i, x + a[i]);}
}signed 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;
}