- 浏览: 35797 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
Ignatius and the Princess III
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4658 Accepted Submission(s): 3263
Problem Description
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
"The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.
Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.
Sample Input
4 10 20
Sample Output
5 42 627
Author
Ignatius.L
做呢题……我领略到思考层层推进果种魅力,同埋果种快感{=__, =}
呢题其实就系组合数学里面既自然数拆分吧,而且最大都只不过系120,所以我首先念到DFS:
DFS(int x, int bx);
x为剩余大小,bx为拆分既上一个数字,例如: 4 = 3 + 1 递归到DFS(1, 3) 当前剩余大小为1,上一个拆分数为3,
bx可以保证拆分无重复,可以参考题目,但系发觉50+就已经超时鸟{= =}
跟住呢个时候我捻到用一维数组做记忆化DFS:
int dp[MAXI];
dp[x]表示数字x既拆分方法有几种,甘样当递归到DFS(int x, int bx)时如果dp[x] > 0就可以直接返回dp[x]。
所以我就直接加入判断:
if (dp[x]) return dp[x];
但系呢个时候有个问题就系,拆分既前一个数bx必须不小于x,先正可以直接返回dp[x],所以我又加入判断:
if (dp[x] && dp[x] <= bx) return dp[x];
但系,都中系超时窝,跟住我就捻到一个例子:10 = 1 + .... 即系当x > bx既时候,会一直递归落去,例如120既全1拆分
就会递归120层,呢种情况我无优化到,所以超时鸟。
跟住我捻到可吾可以构造一个二维数组:
int dp[i][j];
呢个数组记录既系数i第一个拆分数为j既时候拆分方法有几种,点解会甘捻?其实原因真系好简单,因为我地宜家要解决
既问题系x > bx即剩余大小大于前一个拆分数既情况,举个例子:
10 = 2 + .......
其实姐系DFS(8, 2)既情况,因为呢个时候x > bx 所以会进入2~1既循环,继续递归,但系!其实问题可以转化为:
10 = 2 + {8 = 2 + .......}
姐系10第一个拆分数为2既情况其实就系等于8第一个拆分数为2既情况,即dp[8][2]!!,所以如果我地知道dp[8][2],就可以
直接加上而唔洗继续DFS(6, 2),所以我就系循环果度加入判断:
if (!dp[x][i]) dp[x][i] = DFS(x - i, i);
tsu += dp[x][i];
不过呢个时候又出现一个问题,就系如果一开始就DFS(n, n)系无用既,因为dp并无记录n以下既数据,所以我地要做既就系从
1开始做DFS递推上去!
for (i = 0; i <= n; i++) dp[i][i] = DFS(i, i);
最后其实我地不必每次输入都做一次DP,其实初始化做一次,我地就已经保存左所有答案。
for (i = 0; i <= 120; i++) dp[i][i] = DFS(i, i);
每次输入就直接输出dp[n][n]即可,即系俗称打表。
下面AC代码:
4277486 | 2011-07-28 13:31:08 | Accepted | 1028 | 0MS | 296K | 595 B | C++ | 10SGetEternal{(。)(。)}! |
#include <iostream> #include <vector> using namespace std; #define MAXI 122 int dp[MAXI][MAXI], n; int DFS(int x, int bx) { int i; int tsu = 0; if (dp[x][x] && x <= bx) return dp[x][x]; for (i = bx; i >= 1; i--) { if (!dp[x][x - i]) dp[x][x - i] = DFS(x - i, i); tsu += dp[x][x - i]; } return tsu; } int main() { int i, j; for (i = 0; i <= MAXI; i++) for (j = 0; j <= MAXI; j++ ) dp[i][j] = 0; for (dp[0][0] = i = 1; i <= MAXI; i++) dp[i][i] = DFS(i, i); while (scanf("%d", &n) != EOF) printf("%d\n", dp[n][n]); return 0; }
当然我呢种捻法比较复杂,其实自然数拆分可以直接计算,不过我想讲既系思考既层层递进,真会系好爽
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1143Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 828What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1164Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 757find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 989Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 728box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 777Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 961Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1155二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 977Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 856Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 763Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1007分拆素数和 Time Limit: 1000/1000 MS ... -
ZOJ 3512 Financial Fraud .
2011-07-31 20:49 1222Financial Fraud Time Limit: 3 ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1062Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 634Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 567find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 657N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 752Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 636开门人和关门人 Time Limit: 2000/1000 ...
相关推荐
HDUACM2010版03递推求解.ppt
ACM HDU 1404 Digital Deletions(博弈).docx
本资源为HDU数字图像处理课程 浙江省在线平台的视频课后作业 仅供参考 假设我们有一个mat型的单通道图像,命名为srcMat,我们想得到第i行,第j列的像素值则可以用一下的代码 A. int value= srcMat.at(i)(j)[0]; B...
杭电选课插件
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
HDU的一题........HDU DP动态规
Hdu 1020解题报告,http://acm.hdu.edu.cn/showproblem.php?pid=1020
nm where m is the number of integers in the set and n1 ... nm are the integers. All integers will be positive and lie within the range of a 32-bit integer. Output For each problem instance, output a ...
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
hdu5102的ac源码。算法:队列、数据结构、图论、模拟。题意:输入一棵树,输出前k小的点对最短距离dis(i,j)的和。
解题报告|ACM|程序设计参考程序以及题目的分析
You are given the value of m and (f(n,m)?n)⊕n, where ``⊕’’ denotes the bitwise XOR operation. Please write a program to find the smallest positive integer n that (f(n,m)?n)⊕n=k, or determine it ...
2.18.1 HDU4656 卷积取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.19 其它公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.19.1 Polya . . . ....
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU一部分题目原码,大部分是可运行的,可能有几题不完整