BOJ13301

12311 ワード
DP テキストリンク

BOJ13301. タイル装飾


質問する



コード#コード#


タイムアウト.

#include <iostream>

using namespace std;

long long targetN(int x)
{

    if (x == 1)
        return 1;
    else if (x == 0)
        return 0;
    else
        return targetN(x - 1) + targetN(x - 2);
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    long long result = 0;
    long long garo = 1;
    long long sero = 1;
    for (int i = 1; i <= n; i++)
    {
        long long temp = targetN(i);

        if (i == 1)
        {
            result = ((temp) + (temp)) * 2;
        }
        else if (i % 2 == 0)
        {
            sero += temp;
            result = ((temp) + (sero)) * 2;
        }
        else if (i % 2 != 0)
        {
            garo += temp;
            result = ((garo) + (temp)) * 2;
        }
    }

    cout << result << '\n';

    return 0;
}
偶数を入力すると、垂直の長さが増加します.
奇数を入力すると横長が増加します.
増加した長さはフィボナッチ数の積算値と同様に増加した.
長さ増加の横と縦の合計*2
タイムアウトエラーが発生しました...

リファレンス


#include <iostream>

using namespace std;

long long dp1[81];
long long dp2[81];

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    dp1[1] = 1, dp1[2] = 1;
    for (int i = 3; i <= 80; i++)
    {
        dp1[i] = dp1[i - 1] + dp1[i - 2];
    }

    dp2[1] = 4;

    for (int i = 2; i <= 80; i++)
    {
        dp2[i] = dp2[i - 1] + dp1[i] * 2;
    }

    cout << dp2[n] << '\n';
    return 0;
}
賢者の時間...🤨
[白俊]1931号:会議室の手配
20211213-TIL