【USACO 2.3】Zero Sum（dfs）

按字典序输出所有在123..n之间插入' ','-',' '结果为0的表达式。.

http://train.usaco.org/usacoprob2?a=jUh88pMwCSQ&S=zerosum

代码语言：javascript复制

/*
TASK:zerosum
LANG:C  
*/
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
#define N 15
int n;
int k[N],cnt,s[3]={0,1,-1};
string ans[7000];
void dfs(int d){
    if(d>n){
        int sum=0,c=1;
        for(int i=2;i<=n;i  ){
            if(k[i]){
                sum =c;
                c=i*k[i];
            }else{
                c=c*10 (c>0?i:-i);
            }
        }
        sum =c;
        if(sum==0){
            ans[  cnt] ="1";
            for(int i=2;i<=n;i  ){
                ans[cnt] =k[i]>0?' ':k[i]<0?'-':' ';
                ans[cnt] =i '0';
            }
        }
        return;
    }
    for(int i=0;i<=2;i  ){
        k[d]=s[i];
        dfs(d 1);
    }
}
int main(){
    freopen("zerosum.in","r",stdin);
    freopen("zerosum.out","w",stdout);
    scanf("%d",&n);
    dfs(2);
    for(int i=1;i<=cnt;i  ){
        printf("%sn",ans[i].c_str());
    }
}

sum

0 人点赞