POJ 1564 Sum It Up (DFS+剪枝）
http://poj.org/problem?id=1564
dfs
三个参数 x,sum,k, x表示开始的坐标,sum表示当前的和,k表示这是一组答案中的第几个数,是用来记录路径的...
调了好久没写出来...我写完之后答案会有重复.一开始想开一个boolean数组记录,这样第一组样例的3+1就只会输出一遍,但是这样,2+2就不会被记录到答案中了.
然后看了下别人的代码...
卧槽,只是加了个判断...当前的数和上一个如果不同,就继续dfs....
我为何就没想到...这特么是判断重复的直译啊....
1
2 /*************************************************************************
3 > File Name: code/2015summer/0714/K.cpp
4 > Author: 111qqz
5 > Email: rkz2013@126.com
6 > Created Time: 2015年07月16日 星期四 01时03分01秒
7 ************************************************************************/
8
9 #include<iostream>
10 #include<iomanip>
11 #include<cstdio>
12 #include<algorithm>
13 #include<cmath>
14 #include<cstring>
15 #include<string>
16 #include<map>
17 #include<set>
18 #include<queue>
19 #include<vector>
20 #include<stack>
21 using namespace std;
22 #define REP(i, n) for (int i=0;i<int(n);++i)
23 typedef long long LL;
24 typedef unsigned long long ULL;
25 const int N=20;
26 int n,t;
27 int a[N];
28 int ans;
29 int k;
30 int rec[N];
31 bool vis[105];
32 bool ok;
33 void dfs(int x,int sum,int k)
34 {
35 if (sum==t)
36 {
37 ok=true;
38 for ( int i = 0 ; i < k ; i++)
39 {
40 if (i)
41 {
42 printf("+%d",rec[i]);
43 }
44 else
45 {
46 printf("%d",rec[i]);
47 }
48 }
49 printf("\n");
50 return;
51 }
52 int pre = -1;
53 for ( int i = x ; i < n ; i++)
54 {
55 if (sum+a[i]<=t&&a[i]!=pre)
56 {
57 pre = a[i];
58 rec[k] = a[i];
59 dfs(i+1,sum+a[i],k+1);
60 }
61 }
62 }
63 int main()
64 {
65 while (scanf("%d %d",&t,&n)!=EOF&&n)
66 {
67 ok = false;
68 memset(vis,false,sizeof(vis));
69 ans = 0 ;
70 k = 0;
71 for ( int i = 0 ; i < n ; i++)
72 scanf("%d",&a[i]);
73 printf("Sums of %d:\n",t);
74 dfs(0,0,0);
75 if (!ok) printf("NONE\n");
76 }
77
78 return 0;
79 }
80
81
82
83