当前位置: 代码迷 >> 综合 >> poj 1950 Dessert 深搜
  详细解决方案

poj 1950 Dessert 深搜

热度:51   发布时间:2024-01-19 06:18:08.0

题意;

给n,问有多少和由1,2...n,和'+','-',’.‘(表示连接,4.5表示45)组成,值为0的表达式。

分析:

深搜,因为要枚举到“连接”的情况,所以传送pre表示上个表达式中最后一个数字。

代码:

//poj 1950
//sep9
#include <iostream>
using namespace std;
__int64 n,tot,printNum;
__int64 ans[32];void dfs(__int64 sum,__int64 cur,__int64 pre)
{//printf("%I64d\n",sum);if(cur==n+1){if(sum!=0)return ;++tot;if(tot>20)return ;__int64 i;printf("1");for(i=2;i<=n;++i){if(ans[i]==0)printf(" + ");else if(ans[i]==1)printf(" - ");elseprintf(" . ");printf("%d",i);}printf("\n");return ;}	ans[cur]=0;dfs(sum+cur,cur+1,cur);ans[cur]=1;dfs(sum-cur,cur+1,-cur);ans[cur]=2;__int64 digits,newNum;if(cur<10)digits=10;elsedigits=100;	if(pre<0)newNum=pre*digits-cur;elsenewNum=pre*digits+cur; dfs(sum-pre+newNum,cur+1,newNum);
}int main()
{scanf("%I64d",&n);tot=0;printNum=0;dfs(1,2,1);	printf("%I64d",tot);return 0;	
} 


  相关解决方案