P1118 [USACO06FEB] Backward Digit Sums G/S

题目描述

FJ and his cows enjoy playing a mental game. They write down the numbers from $1$ to$ N(1 \le N \le 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.

输入格式

共一行两个正整数 $n,sum$。

输出格式

输出包括一行，为字典序最小的那个答案。

当无解的时候，请什么也不输出。

输入输出样例 #1

输入 #1

4 16

输出 #1

3 1 2 4

说明/提示

• 对于 $40\%$ 的数据，$1\le n\le 7$；
• 对于 $80\%$ 的数据，$1\le n\le 10$；
• 对于 $100\%$ 的数据，$1\le n\le 12$，$1\le sum\le 12345$。

C++实现

#include <bits/stdc++.h>//万能头文件
using namespace std;
int n,p;//输入必备
int a[13];//输出必备
int c[13][13];//杨辉三角必备
bool b[13];//判重必备
void dfs(int dep,int s)
{
if(s>p)
return;
if(dep>n){
if(s==p){
cout<<a[1];
for(int i=2;i<=n;i++)
cout<<" "<<a[i];//输出
exit(0);//终止程序
}
return;//如果没有输出答案，就返回
}
for(int i=1;i<=n;i++){
if(b[i]==false) {
b[i]=true;//标记成用过
a[dep]=i;//保存第dep个取的数
dfs(dep+1,s+i*c[n][dep]);
b[i]=false;//注意这里要将状态回归，不然TLE
}
}
}
int main()
{
cin>>n>>p;//输入
c[1][1]=1;
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];//生成杨辉三角
dfs(1,0);//开启深搜之旅
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容