POJ 3187 Backward Digit Sums——————全排列暴力水题

以你之姓@ 2021-11-16 16:31 200阅读 0赞

# [Backward Digit Sums][] #

Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 10751 Accepted: 6056

**Description**

FJ and his cows enjoy playing a mental game. They write down the numbers from 1 to N (1 <= N <= 10) in a certain order and then sum adjacent numbers to produce a new list with one fewer number. They repeat this until only a single number is left. For example, one instance of the game (when N=4) might go like this:

3   1   2   4
    
      4   3   6
    
        7   9
    
         16

Behind FJ’s back, the cows have started playing a more difficult game, in which they try to determine the starting sequence from only the final total and the number N. Unfortunately, the game is a bit above FJ’s mental arithmetic capabilities.

Write a program to help FJ play the game and keep up with the cows.

**Input**

Line 1: Two space-separated integers: N and the final sum.

**Output**

Line 1: An ordering of the integers 1…N that leads to the given sum. If there are multiple solutions, choose the one that is lexicographically least, i.e., that puts smaller numbers first.

**Sample Input**

4 16

**Sample Output**

3 1 2 4

**Hint**

Explanation of the sample:

There are other possible sequences, such as 3 2 1 4, but 3 1 2 4 is the lexicographically smallest.

**Source**

USACO 2006 February Gold & Silver

--------------------

FJ 和 他的奶牛们在玩一个心理游戏。他们以某种方式写下1至N的数字（1<=N<=10）。 然后把相邻的数相加的到新的一行数。重复这一操作直至只剩一个数字。比如下面是N=4时的一种例子

3   1   2   4
    
      4   3   6
    
        7   9
    
         16

在FJ回来之前，奶牛们开始了一个更难的游戏：他们尝试根据最后结果找到开始的序列。这已超过了FJ的思考极限。

写一个程序来帮助FJ吧

满足要求的一行序列。若有多种情况，输出字典序最小的一种

/*--------- Hongjie ----------*/
    // #include<bits/stdc++.h>
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<map>
    #include<bitset>
    #include<set>
    #include<vector>
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<int ,int> P;
    
    const int INF  = 0x3f3f3f3f;
    const int MAXN = 17;
    int n,m;
    int a[MAXN];
    int b[MAXN][MAXN];
    int main(){
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            while(~scanf("%d %d",&n,&m)) {
        
                    for(int i=1;i<=n;++i)
                            a[i] = i;
                    do {
        
                            for(int i=1;i<=n;++i)
                                    b[1][i] = a[i];
                            for(int i=2;i<=n;++i)
                                    for(int j=i;j<=n;++j)
                                            b[i][j] = b[i-1][j] + b[i-1][j-1];
                            if(b[n][n]==m)
                            {
        
                                    for(int i=1;i<=n;++i)
                                            printf("%d ",a[i]);
                                    cout<<endl;
                                    break;
    
                            }
                    } while(next_permutation(a+1,a+n+1));
            }
            return 0;
    }

[Backward Digit Sums]: http://poj.org/problem?id=3187