[15999]1.2.3プラス4

1172 ワード
アルゴリズム#アルゴリズム# ダイナミック テキストリンク 
#include <iostream>
using namespace std;
int d[10001][4];
int count = 0;
int main(void)
{
    int n;
    cin >> n;
    d[1][1] = 1;
    d[2][1] = 1;
    d[2][2] = 1;
    d[3][1] = 1;
    d[3][2] = 1;
    d[3][3] = 1;
    for (int i = 4; i <= 10000; i++)
    {
        d[i][1] = d[i - 1][1];
        d[i][2] = d[i - 2][2] + d[i - 2][1];
        d[i][3] = d[i - 3][3] + d[i - 3][1] + d[i - 3][2];
    }
    for (int i = 0; i < n; i++)
    {
        int m;
        cin >> m;
        cout << d[m][1] + d[m][2] + d[m][3] << "\n";
    }
    return 0;
}

質問へのアクセス


1,2,3プラスの問題とは異なり,昇順配列の問題のみを計算する.したがって、動的配置は1次元ではなく2次元として宣言されます.

解決策


d[i][1]はiの和を意味し、端数1で充填される.したがって,i−1元素に+1を加えればよい.
したがって、式d[i][1]=d[i-1][1].
d[i][2]は、i要素が末尾2に埋め込まれていることを示す.例えば、iが4であれば、1+1+2または2+2と表すことができる.これは、i−2要素に対して末尾1に+2を加えるか、i−2要素に対して末尾2に+2を加えることに等しい.
d[i][3]は、i要素が末尾3に埋め込まれていることを示す.これは同じ方法です.
d[i][3]=d[i-3][3]+d[i-3][1]+d[i-3][2].
モダンなデザインパターン
Beanstalkで使用されるEC2のSGの設定を変更するには？