HDU 2018雌牛の物語(ベースDP)

5010 ワード

同前ダイナミック企画DP ベースdp 問題を解く

HDU 2018雌牛の物語(ベースDP)
タイトルリンク
HDU2018
に言及
1頭の雌牛がいて、毎年年の初めに1頭の子牛を産んでいます.子牛は4年目から毎年年初にも子牛を産む.プログラミングして実現してn年目の時、何頭の雌牛がありますか?
解析
これは簡単なもので、フィボナッチの数列が押されています.f(1)=1 f(2)=2 f(3)=3 f(4)=4 n>=5に対してf(n)=f(n-1)+f(n-3)(前の3年、n=5に対して2年目に生まれた雌牛も生まれます)そしてなくなります
コード#コード#

#include
#define ll long long
using namespace std;
const int MAXN = 500;
ll ans[MAXN];
int n;
ll solve()
{
	ans[0] = 0;
	ans[1] = 1;
	ans[2] = 2;
	ans[3] = 3;
	ans[4] = 4;
	for (int i = 5; i <= n; i++)
	{
		ans[i] = ans[i-1]+ans[i-3];
	}
	return ans[n];
}
int main()
{
	while (~scanf("%d", &n) && n != 0)
	{
		printf("%lld
", solve());
	}
	return 0;
}

牛客のいくつかの面白い小題

【コンパイル原理】LR(0)構文解析器を実現する