题解 P1473 【零的数列 Zero Sum】

john666 · 2017-10-17 17:23:46 · 题解

速度很快的：

分析：

1、搜索对象为符号位，共n-1个；

2、搜索状态search(int k,int s,int q,char c)；

对于每数字后面可加的符号有空格、+、-三种；

k为第几个，s为当前总和，q为待处理的前一个数值，c为最后一个非空格符号；

3、搜索条件：分别搜索三种符号所得的表达式的和，当k=n且和为0时输出；

4、返回处理：每次返回时需要从上一个数开始向下搜索。

详见代码：

#include<bits/stdc++.h>//john.c_Tae Yeon
#define sea 1000500
using namespace std;
int n,sz[20],ss;
char symbol[20];
void sear(int k,int s,int q,char c){
    if(k==n){
        if(c=='+'){
            s=s+q;
        }
        else{
            s=s-q;
        }
        if(s==0){
            ss++;
            cout<<"1";
            for(int i=1;i<n;i++){
                cout<<symbol[i]<<sz[i];
            }
            cout<<" "<<ss<<endl;
        }
    }
    else{
        symbol[k]=' ';
        sear(k+1,s,q*10+sz[k],c);
        symbol[k]='+';
        if(c=='+'){
            sear(k+1,s+q,sz[k],'+');
        }
        else{
            sear(k+1,s-q,sz[k],'+');
        }
        symbol[k]='-';
        if(c=='+'){
            sear(k+1,s+q,sz[k],'-');
        }
        else{
            sear(k+1,s-q,sz[k],'-');
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        sz[i]=i+1;
    }
    sear(1,0,1,'+');
    return 0;
}