白駿2193号:李親水

リンク:https://www.acmicpc.net/problem/2193

問題を読む

ダイナミックプログラミング.まず始めましょう.
0と1のみからなる数をバイナリ数と呼ぶ.バイナリ数には、バイナリ数と呼ばれる特殊な性質を持つものがあります.初めて聞きましたね
1.このパラメータは0で始まりません.
2.この親水性では、1不連続が2回出現する.これは、11に部分文字列がないことを意味する.
n桁の数でこの親水性の個数を求めます.
前回の2579号:階段を上るの質問から近づいてきたのでしょうか
公比は3 a+bͨ2 a 3^{a+b}*2^{a}3 a+bͨ2 aである.わぁ^^

コード#コード#

#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;

	long long arr[91];
	arr[1] = 1;
	arr[2] = 1;

	for (int i = 3; i <= N; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	cout << arr[N];
	return 0;
}

ぶんせき

まず私が何をしたのか整理してください.まず1で始まる枝と0で始まる枝を計算した.それからこれを3つの位置に刺して、全部でいくつかあることを確認して、それを点火式にしようとしました.残りの人はそれぞれ1と2の状況を計算し、ナスを増やそうとした.無意味な行為ですが^^
最初は間違った接近があった.1-1とは限らないが、1-1-(0/1)が含まれているので、数字がおかしい...
ちゃんと勘定しなさい.何も言えない.状況をよく考えなさい.
点火式は簡単だ.

long long arr[91];
arr[1] = 1;
arr[2] = 1;

for (int i = 3; i <= N; i++) {
	arr[i] = arr[i - 1] + arr[i - 2];
}

ここで注意しなければならないのは、arrをlong longで発表したことです.intが長くなる場合は、intではなくlong longと宣言すべきである.そのため、実際にエラーが発生したのはintと発表されたからです.9桁を超える場合は、そのままlong longに変更しましょう.考えてみれば、90桁だったのにintで装おうとした私はバカだった.