本题就是求一个数是否能写成几个数的阶乘的和的形式,可以当作背包问题,也可以用DFS来解,下面用的贪心
http://poj.org/problem?id=1775
Sum of Factorials
Time Limit:1000MS |
|
Memory Limit:30000K |
|
|
|
Description
John von Neumann, b. Dec. 28, 1903, d. Feb. 8, 1957, was a Hungarian-American mathematician who made important contributions to the foundations of mathematics, logic, quantum physics,meteorology, science, computers, and game theory. He was noted for a phenomenal memory and the speed with which he absorbed ideas and solved problems. In 1925 he received a B.S. diploma in chemical engineering from Zurich Institute and in 1926 a Ph.D. in mathematics from the University of Budapest. His Ph.D. dissertation on set theory was an important contribution to the subject. At the age of 20, von Neumann proposed a new definition of ordinal numbers that was universally adopted. While still in his twenties, he made many contributions in both pure and applied mathematics that established him as a mathematician of unusual depth. His Mathematical Foundations of Quantum Mechanics (1932) built a solid framework for the new scientific discipline. During this time he also proved the mini-max theorem of GAME THEORY. He gradually expanded his work in game theory, and with coauthor Oskar Morgenstern he wrote Theory of Games and Economic Behavior (1944).
There are some numbers which can be expressed by the sum of factorials. For example 9,9=1!+2!+3! Dr. von Neumann was very interested in such numbers. So, he gives you a number n, and wants you to tell him whether or not the number can be expressed by the sum of some factorials.
Well, it's just a piece of cake. For a given n, you'll check if there are some xi, and let n equal to Σ1<=i<=txi!. (t >=1 1, xi >= 0, xi = xj iff. i = j). If the answer is yes, say "YES"; otherwise, print out "NO".
Input
You will get several non-negative integer n (n <= 1,000,000) from input file. Each one is in a line by itself.
The input is terminated by a line with a negative integer.
Output
For each n, you should print exactly one word ("YES" or "NO") in a single line. No extra spaces are allowed.
Sample Input
9
-1
Sample Output
YES
分享到:
相关推荐
北大POJ2739-Sum of Consecutive Prime Numbers 解题报告+AC代码
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
poj2479代码 Maximum sum 对于这道题,我的思路是先从左到右,计算并存储每个节点
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1686093
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
poj 3782 Equal Sum Partitions.md
poj 2771 Guardian of Decency.md
poj 2903 Joy of Mobile Routing.md
poj 3174 Alignment of the Planets.md
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj1087贪心算法实验报告 poj1087贪心算法实验报告
北大POJ2109-Power of Cryptography 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...