POJ 3187 杨辉三角+枚举排列好题

如果给出一个由1~n组成的序列，我们可以每相邻2个数求和，得到一个新的序列，不断重复，最后得到一个数sum，

现在输入n，sum，要求输出一个这样的排列，如果有多种情况，输出字典序最小的那一个。

刚开始我是直接搜，tle了

然后就开始找最初的序列和最终的和有什么关系

因为最终的和sum一定是等于若干个a[1],若干个a[2],...，若干个a[n]的和

即sum=p1*a1+p2*a2+...+pn*an

所以我们只要求出数组a的系数，n个p即可。

然后发现，和杨辉三角有很大的关系。

如果杨辉三角的行数从1开始算的话，

对于某一个1~n的排列得到sum，就需要有n个系数p，发现，这n个系数就刚好是杨辉三角的第n行。

所以对于等式：sum=p1*a1+p2*a2+...+pn*an

知道了n，我们就知道了n个系数p了，sum也知道

所以只要枚举1~n的排列，刚哪一个排列符合等式就ok了

又要字典序顺序，所以我们从小到大的顺序枚举，一有答案了，就跳出来。

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int c[maxn][maxn];

 int a[maxn];

 int n,sum;

 bool flag;

 void init_c()

 {

     memset(c,,sizeof c);

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

     {

         c[i][]=;

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

             c[i][j]=c[i-][j-]+c[i-][j];

     }

 }

 void solve()

 {

     int ret=;

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

     {

         ret+=c[n][i]*a[i];

     }

     if(ret==sum)

     {

         flag=true;

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

             printf("%d ",a[i]);

         printf("%d\n",a[n]);

     }

     return ;

 }

 void next(int cur)

 {

     if(flag)

         return ;

     if(cur==n+)

     {

         solve();

         return ;

     }

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

     {

         int ok=;

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

         {

             if(a[j]==i)

                 ok=;

         }

         if(ok)

         {

             a[cur]=i;

             next(cur+);

         }

     }

 }

 int main()

 {

     init_c();

     while(~scanf("%d%d",&n,&sum))

     {

         flag=false;

         next();

     }

     return ;

 }

巴特西

POJ 3187 杨辉三角+枚举排列好题

最新文章

热门文章

巴特西

POJ 3187 杨辉三角+枚举排列 好题

最新文章

热门文章

POJ 3187 杨辉三角+枚举排列好题