MyException - 我的异常网
当前位置:我的异常网» 编程 » HDU 1028 Ignatius and the Princess III

HDU 1028 Ignatius and the Princess III

www.MyException.Cn  网友分享于:2013-11-20  浏览:6次
HDU 1028 Ignatius and the Princess III .

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!"
 

 

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;
}

 当然我呢种捻法比较复杂,其实自然数拆分可以直接计算,不过我想讲既系思考既层层递进,真会系好爽生气

文章评论

如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员必看的十大电影
程序员必看的十大电影
编程语言是女人
编程语言是女人
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员的鄙视链
程序员的鄙视链
漫画:程序员的工作
漫画:程序员的工作
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
Java程序员必看电影
Java程序员必看电影
如何成为一名黑客
如何成为一名黑客
程序员和编码员之间的区别
程序员和编码员之间的区别
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员都该阅读的书
程序员都该阅读的书
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
中美印日四国程序员比较
中美印日四国程序员比较
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
老程序员的下场
老程序员的下场
我的丈夫是个程序员
我的丈夫是个程序员
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
 程序员的样子
程序员的样子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
总结2014中国互联网十大段子
总结2014中国互联网十大段子
鲜为人知的编程真相
鲜为人知的编程真相
我是如何打败拖延症的
我是如何打败拖延症的
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员应该关注的一些事儿
程序员应该关注的一些事儿
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
那些争议最大的编程观点
那些争议最大的编程观点
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
每天工作4小时的程序员
每天工作4小时的程序员
旅行,写作,编程
旅行,写作,编程
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有