POJ-3187 Backward Digit Sums （暴力枚举）

http://poj.org/problem?id=3187

给定一个个数n和sum，让你求原始序列，如果有多个输出字典序最小的。

暴力枚举题，枚举生成的每一个全排列，符合即退出。

dfs版：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <vector>
 5 #include <cstring>
 6 #include <string>
 7 #include <algorithm>
 8 #include <string>
 9 #include <set>
10 #include <functional>
11 #include <numeric>
12 #include <sstream>
13 #include <stack>
14 //#include <map>
15 #include <queue>
16 
17 #define CL(arr, val)    memset(arr, val, sizeof(arr))
18 
19 #define ll long long
20 #define inf 0x7f7f7f7f
21 #define lc l,m,rt<<1
22 #define rc m + 1,r,rt<<1|1
23 #define pi acos(-1.0)
24 
25 #define L(x)    (x) << 1
26 #define R(x)    (x) << 1 | 1
27 #define MID(l, r)   (l + r) >> 1
28 #define Min(x, y)   (x) < (y) ? (x) : (y)
29 #define Max(x, y)   (x) < (y) ? (y) : (x)
30 #define E(x)        (1 << (x))
31 #define iabs(x)     (x) < 0 ? -(x) : (x)
32 #define OUT(x)  printf("%I64d
", x)
33 #define lowbit(x)   (x)&(-x)
34 #define Read()  freopen("a.txt", "r", stdin)
35 #define Write() freopen("dout.txt", "w", stdout);
36 #define maxn 1000000000
37 #define N 1010
38 using namespace std;
39 
40 int n,sum,flag;
41 int pos[15],num[15],cnt[15],vis[15];
42 
43 bool solve()
44 {
45     for(int i=1;i<=n;i++) num[i]=pos[i];
46     for(int i=n;i>1;i--)
47     {
48         for(int j=1;j<i;j++)
49             num[j]=num[j]+num[j+1];
50     }
51     if(num[1]==sum) return true;
52     return false;
53 }
54 void dfs(int k)
55 {
56     if(flag) return;
57     if(k==n+1)
58     {
59         if(solve())
60         {
61             for(int i=1;i<=n;i++)
62                 if(i==n) printf("%d
",pos[i]);
63                 else printf("%d ",pos[i]);
64             flag=1;
65             return;
66         }
67     }
68     for(int i=1;i<=n;i++)
69     {
70         if(!vis[i])
71         {
72             pos[k]=i;
73             vis[i]=1;
74             dfs(k+1);
75             vis[i]=0;
76         }
77     }
78     return;
79 }
80 int main()
81 {
82     //freopen("a.txt","r",stdin);
83    // freopen("b.txt","w",stdout);
84     scanf("%d%d",&n,&sum);
85     memset(vis,0,sizeof(vis));
86     flag=0;
87     dfs(1);
88    return 0;
89 }

View Code

stl版：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int n,sum,pos[15];
 6 
 7 bool check()
 8 {
 9     int dp[15];
10     for(int i=1;i<=n;i++)
11         dp[i]=pos[i];
12     for(int i=n;i>1;i--)
13     {
14         for(int j=1;j<i;j++)
15         {
16             dp[j]=dp[j]+dp[j+1];
17         }
18     }
19     if(dp[1]==sum) return true;
20     return false;
21 }
22 
23 void pri()
24 {
25     for(int i=1;i<=n;i++)
26         if(i==n) printf("%d
",pos[i]);
27         else printf("%d ",pos[i]);
28 }
29 void dfs()
30 {
31     for(int i=1;i<=n;i++)
32         pos[i]=i;
33     do {
34         if(check()) {pri();break;}
35     }while(next_permutation(pos+1,pos+n+1));
36 }
37 int main()
38 {
39     scanf("%d%d",&n,&sum);
40     dfs();
41     return 0;
42 }

View Code