dfs做法,请问这道题的记忆化搜索要怎么加?
查看原帖
dfs做法,请问这道题的记忆化搜索要怎么加?
671260
Nekomusume楼主2023/6/23 23:56
#include <iostream>
using namespace std;
int a[105], n, m, ans = 0, flag[105], sum = 0;
void dfs(int x)
{
    if(sum == m){ans++; return;}
    if(sum > m)return;
    for(int i = x + 1; i <= n; i++)
    {
        if(flag[i] == 0)
        {
            flag[i] = 1;
            sum += a[i];
            dfs(i);
            flag[i] = 0;
            sum -= a[i];
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    dfs(0);
    cout << ans << endl;
    return 0;
}

当参数为x时调用f[x],但是f数组里面要存什么东西呢

2023/6/23 23:56
加载中...