NYoj1058

水题，dfs，裸的，本来这道题没什么好写的，只是第一次写的代码慢的出奇，纪念一下那个奇怪的思路

链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=1058

慢得出奇的代码，必须TLE：

 1  
 2  
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<string>
 7 #include<cmath>
 8 #include<algorithm>
 9 #include<vector>
10 using namespace std;
11 const int maxn=22;
12 int a[maxn];
13 int n;
14 int flag;
15 vector <int> p;
16 int t;
17 int c[maxn];
18 int j;
19 void dfs(int k,int *vis,int cur)
20 {
21     long long cnt=0;
22     if(cur==n)
23     {
24         int flag1=0;
25         for(int i=0;i<cur;i++)
26             if(vis[i])
27         {
28             cnt+=a[i];
29             if(cnt==k)
30             {
31                 flag=1;
32                 flag1=1;
33                 t=i;
34                 break;
35             }
36         }
37         if(flag1)
38         {
39              j=0;
40             for(int i=0;i<=t;i++)
41             {
42                 if(vis[i])
43                 c[j++]=i;
44             }
45            // p.clear();
46         }
47             return;
48     }
49     vis[cur]=1;
50     dfs(k,vis,cur+1);
51     vis[cur]=0;
52     dfs(k,vis,cur+1);
53 }
54 int main()
55 {
56     int k;
57     int vis[maxn];
58     while(scanf("%d",&n)!=EOF)
59     {
60         scanf("%d",&k);
61         for(int i=0;i<n;i++)
62             scanf("%d",&a[i]);
63         flag=0;
64         dfs(k,vis,0);
65         if(flag)
66         {
67             printf("YES
");
68             for(int i=0;i<j-1;i++)
69                 printf("%d ",a[c[i]]);
70             printf("%d
",a[c[j-1]]);
71         }
72         else
73             printf("NO
");
74     }
75     return 0;
76 }
77

View Code

之后改良思路以后AC掉了，AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<cmath>
 6 #include<vector>
 7 using namespace std;
 8 const int maxn=22;
 9 int a[maxn],vis[maxn];
10 int n,k;
11 bool dfs(int sum,int i)
12 {
13     if(i==n) return sum==k;
14     if(dfs(sum,i+1))
15     {
16         vis[i]=0;
17         return true;
18     }
19     if(dfs(sum+a[i],i+1))
20     {
21         vis[i]=1;
22         return true;
23     }
24     return false;
25 }
26 int main()
27 {
28     while(cin>>n>>k)
29     {
30         for(int i=0;i<n;i++)
31             scanf("%d",&a[i]);
32         memset(vis,0,sizeof(vis));
33         if(dfs(0,0))
34         {
35             printf("YES
");
36             int k;
37             for(int i=0;i<22;i++)
38                 if(vis[i])
39             {
40                 k=i;
41                 printf("%d",a[i]);
42                 break;
43             }
44             for(int i=k+1;i<22;i++)
45                 if(vis[i])
46                 printf(" %d",a[i]);
47         }
48         else
49         {
50             printf("NO");
51         }
52         printf("
");
53     }
54     return 0;
55 }

View Code

考研前最后一篇博客，博客园停止更新到12月28日，