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

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

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

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

dfs版：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <string>

 #include <set>

 #include <functional>

 #include <numeric>

 #include <sstream>

 #include <stack>

 //#include <map>

 #include <queue>

 #define CL(arr, val)    memset(arr, val, sizeof(arr))

 #define ll long long

 #define inf 0x7f7f7f7f

 #define lc l,m,rt<<1

 #define rc m + 1,r,rt<<1|1

 #define pi acos(-1.0)

 #define L(x)    (x) << 1

 #define R(x)    (x) << 1 | 1

 #define MID(l, r)   (l + r) >> 1

 #define Min(x, y)   (x) < (y) ? (x) : (y)

 #define Max(x, y)   (x) < (y) ? (y) : (x)

 #define E(x)        (1 << (x))

 #define iabs(x)     (x) < 0 ? -(x) : (x)

 #define OUT(x)  printf("%I64d\n", x)

 #define lowbit(x)   (x)&(-x)

 #define Read()  freopen("a.txt", "r", stdin)

 #define Write() freopen("dout.txt", "w", stdout);

 #define maxn 1000000000

 #define N 1010

 using namespace std;

 int n,sum,flag;

 int pos[],num[],cnt[],vis[];

 bool solve()

 {

     for(int i=;i<=n;i++) num[i]=pos[i];

     for(int i=n;i>;i--)

     {

         for(int j=;j<i;j++)

             num[j]=num[j]+num[j+];

     }

     if(num[]==sum) return true;

     return false;

 }

 void dfs(int k)

 {

     if(flag) return;

     if(k==n+)

     {

         if(solve())

         {

             for(int i=;i<=n;i++)

                 if(i==n) printf("%d\n",pos[i]);

                 else printf("%d ",pos[i]);

             flag=;

             return;

         }

     }

     for(int i=;i<=n;i++)

     {

         if(!vis[i])

         {

             pos[k]=i;

             vis[i]=;

             dfs(k+);

             vis[i]=;

         }

     }

     return;

 }

 int main()

 {

     //freopen("a.txt","r",stdin);

    // freopen("b.txt","w",stdout);

     scanf("%d%d",&n,&sum);

     memset(vis,,sizeof(vis));

     flag=;

     dfs();

    return ;

 }

stl版：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,sum,pos[];

 bool check()

 {

     int dp[];

     for(int i=;i<=n;i++)

         dp[i]=pos[i];

     for(int i=n;i>;i--)

     {

         for(int j=;j<i;j++)

         {

             dp[j]=dp[j]+dp[j+];

         }

     }

     if(dp[]==sum) return true;

     return false;

 }

 void pri()

 {

     for(int i=;i<=n;i++)

         if(i==n) printf("%d\n",pos[i]);

         else printf("%d ",pos[i]);

 }

 void dfs()

 {

     for(int i=;i<=n;i++)

         pos[i]=i;

     do {

         if(check()) {pri();break;}

     }while(next_permutation(pos+,pos+n+));

 }

 int main()

 {

     scanf("%d%d",&n,&sum);

     dfs();

     return ;

 }

巴特西

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

最新文章

热门文章