请问是否有记搜优化的递归解法?我研究了半天没写出来,以下为原始版。感谢大佬赐教
查看原帖
请问是否有记搜优化的递归解法?我研究了半天没写出来,以下为原始版。感谢大佬赐教
394113
zly1783598949楼主2022/1/19 16:36
#include <bits/stdc++.h>
using namespace std;

int a[1001];
int ans;
int sum;//从这一节点到子节点的链上的和 
void dfs(int loc,int len)
{
	if(loc > len)
	{
		ans += sum;
		return;
	}
	//
	sum += a[loc]; //选这个 
	dfs(loc+1,len);// 
	//
	sum -= a[loc]; //不选这个
	dfs(loc+1,len);
}

int main()
{
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	
	int x,i=0;
	while( cin >> x )
	{
		a[++i] = x;
	}
	dfs(1,i);
	cout << ans <<endl;
	return 0;
}

2022/1/19 16:36
加载中...