PID563 / [AHOI2010]搬砖头
题目描述

搬砖头

小可可一直对中国五千年的古老文明非常感兴趣,学习历史知识之余,他报名参加了少年考古队,跟随正式的考古队进行考古发掘,通过实践来更好的领会书本知识。这次考古队发现了一个非常巨大的古墓,具有非常高的考古价值,小可可随队来到了考古现场。经过紧张的发掘,古墓的墓道终于显露出来,但是它被一块块方砖封住了,现在小可可的任务就是帮助考古队将这些方砖移走,打通墓道。由于这些保存完好的古代方砖也是珍贵的文物,所以规定一次最多只能搬三块砖。小可可在搬砖的过程中一直在思考一个问题,他很想知道将这些砖头搬走共有多少种不同的搬法。

例如,现在总共有4个砖头,那么可以选择的方法有以下7种:

1,1,1,1(分4次搬完,每次搬一个砖头)

1,2,1(分3次搬完,第一次搬一个,第二次搬两个,第三次搬一个)

1,1,2(分3次搬完,第一次搬一个,第二次搬一个,第三次搬两个)

2,1,1(分3次搬完,第一次搬两个,第二次搬一个,第三次搬一个)

2,2(分2次搬完,第一次搬两个,第二次搬两个)

1,3(分2次搬完,第一次搬一个,第二次搬三个)

3,1(分2次搬完,第一次搬三个,第二次搬一个)

你能不能帮助小可可解决这个问题呢?

输入格式

共一行。是一个1~1000的正整数N,表示共有N块砖头。

输出格式

共一行。输出一个正整数表示N块砖头移动的方法数。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论