P1118 [USACO06FEB]Backward Digit Sums G/S

题解:
  (1)暴力法。对1~N这N个数做从小到大的全排列,对每个全排列进行三角形的计算,判断是否等于N。
  对每个排列进行三角形计算,需要O(N2)次。例如第1行有5个数{a,b,c,d,e},那么第2行计算4次,第3行计算3次…等等,总次数是O(N2)的。
  a    b    c    d    e
    a+b    b+c   c+d   d+e
      a+2b+c b+2c+d c+2d+e
       a+3b+3c+d b+3c+3d+e
          a+4b+6c+4d+e
  共有N!=4亿个排列,总复杂度是O ( N ! N 2 ) 的,显然会超时。
  2)三角计算优化+剪枝。
  1)三角计算的优化。对排列进行三角形计算,并不需要按部就班地算,比如{a,b,c,d,e}这5个数,直接算最后一行的公式a+4b+6c+4d+e就好了,复杂度是O(N)的。

不同的N有不同的系数,比如5个数的系数是{1,4,6,4,1},提前算出所有N的系数备用。可以发现,这些系数正好是杨辉三角。
  2)剪枝。即使有了杨辉三角的优化,总复杂度还是有O(N!N),所以必须进行最优性剪枝。对某个排列求三角形和时,如果前面几个元素和已经大于sum,

那么后面的元素就不用再算了。例如,N=9时,计算到排列{2,1,3,4,5,6,7,8,9},如果前5个元素{2,1,3,4,5}求和已经大于sum,那么后面的{6,7,8,9}~{9,8,7,6}都可以跳过,

下一个排序从{2,1,3,4,6,5,7,8,9}开始。本题sum≤12345,和不大,用这个简单的剪枝方法可以通过。
  3)可以用DFS求全排列,也可以直接用STL 的next_permutation()求全排列。

#include <cstdio>
using namespace std; int n,sum;
//以下所有数组的大小都比所需值稍大,是为了防止越界
int visited[25]={0}; //防止重复选数,这是 dfs 枚举排列的要点
int ans[25]; //放置答案
int pc[25];//构造所有i C n-1 int dfs(int i,int num,int v); //写函数原型是(我的)好习惯! int main(void){
scanf("%d%d",&n,&sum);
//下面构造杨辉三角(即组合数表)
pc[0]=pc[n-1]=1; //杨辉三角性质,两边都是1
if (n>1)
for (int i=1;i*2<n;i++)
pc[i]=pc[n-1-i]=(n-i)*pc[i-1]/i; //利用杨辉三角对称性和组合数公式计算
//下面枚举计算
if (dfs(0,0,0)) //0 仅起占位符作用
for (int i=1;i<=n;i++)
printf("%d ",ans[i]); //输出答案
return 0;
} int dfs(int i,int num,int v){
//参数说明:i 表示已经枚举了前 i 个数(数的序号从 1 开始),num 表示第 i 个数是 num,v 表示前 i 个数的“和”为 v
//返回值说明:返回 0 表示不行(不可能),返回 1 表示找到了可行解。利用返回值就可以在找到第一个解后直接返回了
if (v>sum) //“剪枝”,及时排除不可能情况,加速枚举
return 0; //不可能
if (i==n){ //已经枚举了前 n 个(全部),判断一下是否是可行解
if (v==sum){
ans[i]=num; //放置解
return 1;
}
else
return 0;
}
visited[num]=1; //标记一下“第 i 个数的值已经使用过了”
//下面寻找第 i+1 个数
for (int j=1;j<=n;j++){
if (!visited[j] && dfs(i+1,j,v+pc[i]*j)){ //v+pc[i]*j表示前(i+1)个数的“和”
//注意,如果数的序号从 1 开始,那么第 i 个数的系数实际上是 (i-1) C (n-1)
//执行到这里表示已经找到了可行的解
ans[i]=num;
return 1;
}
}
visited[num]=0; //如果没有找到,一定记得复位,为进一步的寻找做准备
return 0; //执行到这里一定是没有找到解
}

最新文章

  1. 菜鸟学Struts2——HelloWorld
  2. 虚拟机安装CentOS6.4
  3. 负margin的移位参考线
  4. knockoutjs+ jquery pagination+asp.net web Api 实现无刷新列表页
  5. Nancy之基于Nancy.Hosting.Self的小Demo
  6. WPF之Binding
  7. jquery下常用正则表达式整理(可直接粘贴使用)
  8. 【C#公共帮助类】 Utils最全的系统帮助类
  9. mac osx 制作安装u盘
  10. js生成有缩进的表格
  11. php 安装xdebug扩展
  12. 【转】MySQL GRANT REVOKE用法
  13. 使用Underscore.js的template将Backbone.js的js代码和html代码分离
  14. skip-grant-tables:非常有用的mysql启动参数
  15. 应用hexo(rss插件)
  16. [Swift]LeetCode285. 二叉搜索树中的中序后继节点 $ Inorder Successor in BST
  17. 微信小程序 获取用户信息授权
  18. Luminar 3 for Mac(照片编辑工具)v3.1.0中文特别版
  19. 输入系统:epoll &amp; inotify
  20. smarty获取php中的变量

热门文章

  1. Docker入门第三章
  2. ELK+kafka docker快速搭建+.NetCore中使用
  3. Notes about multiboot usb creator
  4. 阿里云云服务器 ECS和云数据库 PolarDB的简单使用
  5. RabbitMQ和Elasticsearch的使用笔记
  6. SQL 练习3
  7. noip 模拟4
  8. webpack编译遇到的问题:Error: Cannot find module &#39;webpack-cli/bin/config-yargs&#39;
  9. java获取真实ip工具类
  10. SpringBoot-2-1-6-集成activiti7-1-0-M4