题目链接

思路:设一开始的n个数为a1、a2、a3...an,一步一步合并就可以用a1..an表示出最后剩下来的数,不难发现其中a1..an的系数恰好就是第n层杨辉三角中的数。所以我们可以先处理出第n层杨辉三角中的数,然后根据这一层中的数搜索即可。

#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<string>
#include<sstream>
#include<cstring>
using namespace std;
int n=0,sum=0,t[20],ans[20];
bool flag=false,book[20];//flag表示是否已经得出答案
void dfs(int x,int y)
{
//如果已经得出答案或者当前的和大于给定的和,就结束搜索
if(flag||y>sum) return;
if(x>n)//表示已经搜完
{
if(y==sum)//如果当前答案等于给定的和
{
for(int i=1;i<=n;i++) printf("%d ",ans[i]);//就输出答案
flag=true;//标记已经得出答案,因为数是从小到大枚举的,所以第一个出现的答案一定是字典序最小。
}
return;
}
for(int i=1;i<=n;i++)//枚举当前数
if(!book[i])//如果这个数还没被用过
{
book[i]=true;//标记
ans[x]=i;//记录
dfs(x+1,y+t[x]*i);//搜索
ans[x]=0;//回溯
book[i]=false;//回溯
}
}
int main()
{
scanf("%d%d",&n,&sum);
t[1]=1;
for(int i=2;i<=n;i++)//预处理第n层出的杨辉三角
for(int j=i;j>=1;j--) t[j]+=t[j-1];
dfs(1,0);//搜索
return 0;
}

最新文章

  1. .NET项目集成VS混淆加密
  2. Python学习笔记之条件、循环和其他语句
  3. 【HDU 2853】 KM算法
  4. 抽象工厂模式(Abstract Factory)
  5. Python—装饰器
  6. 自定义UISearchBar外观
  7. ruby -- 问题解决(二)rails4.0create引起的ActiveModel::ForbiddenAttributesError错误
  8. 闲聊CSS之关于clearfix--清除浮动[转]
  9. CCF 201312-4 有趣的数 (数位DP, 状压DP, 组合数学+暴力枚举, 推公式, 矩阵快速幂)
  10. lintcode:数字三角形
  11. JavaEE通过response实现请求重定向
  12. Android-67-Tomcat启动出错:Server Tomcat v7.0 Server at localhost failed to start.
  13. 博客迁移至 http://www.loveli.site
  14. zookeeper web ui--&amp;gt;node-zk-browser安装
  15. Video Target Tracking Based on Online Learning—深度学习在目标跟踪中的应用
  16. CSS3@media媒体查询
  17. JavaSE_坚持读源码_HashMap对象_get_Java1.7
  18. mysql case when 判断null
  19. 最精简的自定义.net 开发框架
  20. 文件替换(交互式)Replace

热门文章

  1. HTML+CSS+JS设计注册页面
  2. gentoo(贱兔) Linux作业系统的基本使用
  3. Grid 网格布局详解
  4. 【PHP数据结构】链表的其它形式
  5. html 随笔-水平控件不对齐的解决办法
  6. Java基础系列(27)- 什么是方法
  7. python的列表和java的数组有何异同
  8. MyBatis-Plus代码生成器的使用
  9. AT4353-[ARC101D]Robots and Exits【LIS】
  10. Spirit带你彻底搞懂JS的6种继承方案