【DFS练习】Pku1950 Dessert-C++

这道题和这道题很类似。

这里还是说一下坑点，因为前一道题’等式’的加数只有9个，但是这道题目最大到了15，所以在选择不加符号的时候需要判断是用100去乘还是用10去乘就可以了。

基本代码稍微把相关的9改成n就可以了。具体思路去看一下前面那篇博客哈，下面就直接贴代码了。

#include<bits/stdc++.h>

using namespace std;

int n,cnt=0;

int num[16];//0.1+2-

bool flag;

void dfs(int sum)

{

	if(sum==n+1)

	{

		int q=0,p;

		for(int i=1;i<=n;)

		{

			if(num[i]==1)flag=1;

			if(num[i]==2)flag=0;

			p=i;

			i++;

			while(!num[i]&&i<=n)

			{

				if(i<10)

					p=p*10+i;

				else p=p*100+i;

				i++;

			}

			if(flag)q+=p;

			else q-=p;

		}

		if(q==0)

		{

			cnt++;

			if(cnt<=20)

			{

				cout<<1;

				for(int i=2;i<=n;i++)

				{

					if(num[i]==1)cout<<" + ";

					if(num[i]==2)cout<<" - ";

					if(num[i]==0)cout<<" . ";

					cout<<i;

				}

				cout<<endl;

			}

		}

		return;

	}

	num[sum]=1;

	dfs(sum+1);

	num[sum]=2;

	dfs(sum+1);

	num[sum]=0;

	dfs(sum+1);

	return;

}

int main()

{

	cin>>n;

	num[1]=1;

	dfs(2);

	cout<<cnt<<endl;

	return 0;

}

ov.

巴特西

【DFS练习】Pku1950 Dessert-C++

最新文章

热门文章