[BOJ][9461]波の半数列
1106 ワード
質問する
トラブルシューティングポリシー
//1 1 1 2 2 3 4 5 7 9
//1 2 3 4 5 6 7 8 9 10
p(5) = p(0) + p(4)
p(6) = p(1) + p(5)
p(7) = p(2) + p(6)
p(8) = p(7) + p(3)
p(9) = p(8) + p(4)
p(10) = p(9) + p(5)
pは波の半数列です.
点火式を確立し、p(n)=p(n-1)+p(n-5)を見つけることができる.
コード#コード#
//9461
#include <iostream>
using namespace std;
typedef long long ll;
ll dp[100000] = {
0,
1,
1,
1,
2,
2,
3,
4,
5,
7,
9,
};
ll waveNum(int n)
{
if (n <= 10) return dp[n];
else if(dp[n]) return dp[n];
else if (dp[n] == 0) return dp[n] = waveNum(n - 1) + waveNum(n - 5);
return dp[n];
}
int main()
{
int t; cin >> t;
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for (int i = t; i > 0; i--){
int n; cin >> n;
cout << waveNum(n) << '\n';
}
}
Reference
この問題について([BOJ][9461]波の半数列), 我々は、より多くの情報をここで見つけました
https://velog.io/@easttwave/BOJ9461-파도반-수열
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
//9461
#include <iostream>
using namespace std;
typedef long long ll;
ll dp[100000] = {
0,
1,
1,
1,
2,
2,
3,
4,
5,
7,
9,
};
ll waveNum(int n)
{
if (n <= 10) return dp[n];
else if(dp[n]) return dp[n];
else if (dp[n] == 0) return dp[n] = waveNum(n - 1) + waveNum(n - 5);
return dp[n];
}
int main()
{
int t; cin >> t;
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for (int i = t; i > 0; i--){
int n; cin >> n;
cout << waveNum(n) << '\n';
}
}Reference
この問題について([BOJ][9461]波の半数列), 我々は、より多くの情報をここで見つけました https://velog.io/@easttwave/BOJ9461-파도반-수열テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol