NYOJ 25201串dp

935 ワード

01列
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
2
説明
ACMのzycは01列を研究しています.彼はある01列の長さを知っていますが、「11」の子列を含まないこのような長さの01列が何個あるか知りたいと思っています.彼はあなたが彼を助けてほしいと思っています.
注:01列の長さが2の場合、3種類:00,01,10があります.
入力
1行目には整数n(0その後、n行があり、各行に整数m(2<=m<=40)があり、01列の長さを表す.
しゅつりょく
出力に「11」のサブストリングを含まないこの長さの01ストリングは、合計何個あり、1行を占めます.
サンプル入力

2
2
3

サンプル出力

3
5

これはフィボナッチ数列に適合するdp問題であり、動的移動方程式:dp[i]=dp[i-1]+dp[i-2].
説明:長さiの01列の構成:長さi-1の列の末尾の0の個数*2+長さi-1の列の末尾の1の個数*1で、長さi-1の末尾の0の個数は長さi-2の列の個数に等しく、等量置換後は上の転移方程式である.

#include<stdio.h>
int main()
{
	int n,m,i,dp[42];
	dp[2]=3,dp[3]=5;
	for(i=4;i<=40;i++)
		dp[i]=dp[i-1]+dp[i-2];
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&m);
		printf("%d
",dp[m]);
	}
	return 0;
}

[Vue.js]親から子へデータを渡す

ツリー配列の離散化Ultra-QuickSort