白駿9431波半数列

6540 ワード
白駿銀器を破壊する テキストリンク

質問する



質問リンク:https://www.acmicpc.net/problem/9461

ポリシー

  • ルールを見つけなければなりません.これは何かルールがあるように見える問題だからです.高校時代に点火式を解いた記憶をすべて取り戻せばいい.
  • の数列は、1 1 1 1 2 3 4 7 9 16 21の場合、5つ繰り返します.3=2+1,4=3+1,5=4+1,7=5+2,9=7+2これらのルールを知っていれば,次のような式が得られる.A(n+1) = A(n) + A(n-5)
    • 注意
  • オーバーフローが発生する可能性があります!

    • コード#コード#

    #include<bits/stdc++.h>

using namespace std;

#define mine

int N;
long long dp[101];
long long waveSeq(int n){
    if(n <= 0) return 0;
    long long& ret = dp[n];
    if(ret != -1) return ret;

    return ret = waveSeq(n-5) + waveSeq(n-1);

}
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    memset(dp, -1, sizeof(dp));
    dp[1] = 1;
    dp[2] = 1;
    dp[3] = 1;
    dp[4] = 2;
    dp[5] = 2;
    for(int i=0; i<N; i++){
        int tmp;
        cin >> tmp;
        cout << waveSeq(tmp) << endl;
    }

    return 0;
}

    感想


    オーバーフローを常にチェックするためには、最大値の習慣を身につけるべきです.
    プログラマコード問題2021、09/14-Lv.2入室チェックアウト
    [伯俊]1389ケビン・ベーコンの6次法則