Zero Sum_usaco2.3.3_dfs

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

題目描述 Description


請考慮一個由 1 到 N(N=3, 4, 5 … 9)的數字組成的遞增數列:1 2 3 … N.
現在請在數列中插入“ ”表示加,或者“-”表示減,抑或是“(空格)”表示空白,來將每一對數字組合在一起(請不在第一個數字前插入符號).
計算該表示式的結果並注意你是否得到了和為零.
請你寫一個程式找出所有產生和為零的長度為 N 的數列.

輸入描述 Input Description


單獨的一行表示整數 N (3 <= N <= 20).

輸出描述 Output Description


按照 ASCII 碼的順序,輸出所有在每對數字間插入“ ”, “-”, 或 “ ”後能得到和為零的數列.

(注意:應該保留空格)

分析 Analysis


先刷一發233
dfs一下當前位置填 、-和不填的情況,找到和為0的就輸出,搜尋的時候按照字典序搜就可以了
string讀入和輸出蛋疼,蛋疼,蛋疼

程式碼 Source Code


/*
ID:wjp13241
PROG:zerosum
LANG:C  
*/
#include <string>
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("zerosum.in");
ofstream fout("zerosum.out");
int n;
void dfs(int dep,int sum,string form,int num)
{
if (dep==n)
{
if (sum num==0)
fout<<form<<endl;
return;
}
if (num>=0)
dfs(dep 1,sum,form ' ' char(dep 1 48),num*10 dep 1);
else
dfs(dep 1,sum,form ' ' char(dep 1 48),num*10-dep-1);
dfs(dep 1,sum num,form ' ' char(dep 1 48),dep 1);
dfs(dep 1,sum num,form '-' char(dep 1 48),-dep-1);
}
int main()
{
fin>>n;
dfs(1,0,"1",1);
return 0;
}

相關文章

程式語言 最新文章