【POJ - 1950】Dessert（dfs）

sky-stars 2019-07-18 原文

【POJ – 1950】Dessert（dfs）

–>Dessert

Descriptions:

给你一个数N（3<=N<=15);每个数之间有三种运算符“‘+’，‘-’，‘.’”。输出和值等于零的所有的运算情况及次数num，如果num大于20，则只输出前20中情况。运算符‘.’相当于连接符，例如：11.22 <-> 1122.

Sample Input

Sample Output

1 + 2 - 3 + 4 - 5 - 6 + 7
1 + 2 - 3 - 4 + 5 + 6 - 7
1 - 2 + 3 + 4 - 5 + 6 - 7
1 - 2 - 3 - 4 - 5 + 6 + 7
1 - 2 . 3 + 4 + 5 + 6 + 7
1 - 2 . 3 - 4 . 5 + 6 . 7
6

题目链接

https://vjudge.net/problem/POJ-1950

用dfs深搜，如果和值sum=0，则num++；注意‘.’的处理，需要用一个pre记录上一个数字，如果遇到‘.’则回溯到第一个不为‘.’的符号，注意不管怎么样都会多加或多减一个pre；

必须用scanf，prinf，不然超时

加上ios_base::sync_with_stdio(0); cin.tie(0);都没用为什么啊大佬留言告诉我一下呗

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 30
using namespace std;
int n;
int cnt;
char op[Maxn];//符号
//第x为数，当前式子总和，前一个数
void dfs(int x,int ans,int pre)
{
    if(x==n)
    {
        if(ans==0)
        {
            cnt++;
            if(cnt<=20)//保证只输出前20组的答案
            {
                for(int i=1; i<n; i++)//注意输出格式 WA了无数遍
                    printf("%d %c ",i,op[i]);
                printf("%d\n",n);
            }
        }
        return;
    }
    else
    {
        int now;
        op[x]='+';//第x个符号
        dfs(x+1,ans+x+1,x+1);
        op[x]='-';
        dfs(x+1,ans-(x+1),x+1);
        op[x]='.';
        if(x+1>9)//如果x==9,则其后一位x+1=10，9.10 <-> 910;
            now=pre*100+x+1;
        else
            now=pre*10+x+1;
        int j=x-1;
        while(op[j]=='.'&&j>=0)//找到在符号'.'前面所遍历过中第一个不为'.'的符号；
            j--;
        if(op[j]=='+')
            dfs(x+1,ans-pre+now,now);//前面多加了一个pre，减回来；
        else
            dfs(x+1,ans+pre-now,now);//前面多减了一个pre，加回来；
    }
    return;
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n)//必须用scanf，prinf，不然超时
    {
        cnt=0;////计算符合条件的个数
        op[0]='+';//第一个数之前的符号默认为+
        dfs(1,1,1);
        printf("%d\n",cnt);
    }
}