P5194-Scales S - 从萌新到萌新的成长历程

题目传送门

题目思路

思路比较简单，暴力DFS搜就能70分。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, c;
int ans = 0;

void dfs(vector<int> &a, long long sum, int index)
{
    if (sum > c)
        return;
    if (index == -1)
    {
        if (sum > ans)
            ans = sum;
        return;
    }
    dfs(a, sum + a[index], index - 1);
    dfs(a, sum, index - 1);
}

int main()
{
    cin >> n >> c;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    dfs(a, 0, n - 1);
    cout << ans << endl;
    return 0;
}

问题在于优化来降低时间复杂度。

考虑剪枝，也就是如果前面的和可以全部拿走，那就直接拿走，不再搜索。

AC代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, c;
int ans = 0;

void dfs(vector<int> &a, long long sum, int index, vector<long long> &s)
{
    if (sum > c)
        return;
    if (index == -1)
    {
        if (sum > ans)
            ans = sum;
        return;
    }
    if (sum + s[index] <= c)
        dfs(a, sum + s[index], -1, s);
    else
    {
        dfs(a, sum + a[index], index - 1, s);
        dfs(a, sum, index - 1, s);
    }
}

int main()
{
    cin >> n >> c;
    vector<int> a(n);
    vector<long long> s(n, 0);
    cin >> a[0];
    s[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        cin >> a[i];
        s[i] = a[i] + s[i - 1];
    }
    dfs(a, 0, n - 1, s);
    cout << ans << endl;
    return 0;
}