hdu 5366 The mook jong動的計画(BC 50 C題)

试合の时はまだできていないで、BCはまた1题をして、また点数を落とすことを予想して、ゆっくりと升格して、どのみち1题の运命を终えます...
考え方:
ダイナミックプランニングですが、習い始めたばかりで、できませんよ.のまず法則を探して半日探したが、結局何も見つからず、また深く探し始めた.
结果サンプルが过ぎて、提出がタイムアウトして、深さが大きすぎて、正确な推定がありません..試合後に問題解を見て、動態計画は本当に神算法で、簡単な数行は
できました.配列d[n]を床総数(n>3)を表し、状態遷移方程式d[n]=d[n−1]+(d[n−3]+1)をリストする.できる
このように理解して、nはn-1の床に1つの床を加えて、私たちはこの新しい床に対して分析することができて、彼の上に杭を置かない時、前のn-1
つにはd[n-1]の方法があり、その上に杭を置く場合、2つの杭の間に少なくとも2つの床が必要であるため、n-3つの床しかない
杭を置く、すなわちd[n−3]は、新たに追加された床にのみ杭を置く場合も最後の+1と考えられる..
コード:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
	long long int d[61];
	int i,n;
	d[1] = 1;
	d[2] = 2;
	d[3] = 3;
	for(i=4; i<=60; i++)
		d[i] = d[i-1] + (d[i-3]+1);
	while(cin >> n)
		cout << d[n] << endl; 
	return 0;
}