POJ 1953 基础的DP递推思想

题意:求t个n位的2进制数中,有多少个没有连续的1.

dp0[x]表示以0开头长度为x的这类01串的个数,dp1[x]表示以1开头长度为x的这类01串的个数

dp0[x] = dp0[ x-1 ] + dp1[ x-1 ], dp0[1] = 1;

dp1[x] = dp0[ x-1 ] , dp1[1] = 1;

合并 dp0[x] + dp1[x] = dp0[x-1] + dp1[x-1] + dp0[x-1]
又dp0[x-1] = dp0[x-2] + dp1[x-2]
得:
ans[i] = ans[i-1] + ans[i-2]
由于第i位可任选0或1:
选1时,i-1位选0,i-2位选1的合法
选0时,i-1位选1,i-2位选0的合法
# include <iostream>
# include <algorithm>
using namespace std;

const int _ = 0;
long long ans[50] = {0};

int t, n;

int main()
{
    int i;
    ans[1] = 2LL, ans[2] = 3LL;
    for ( i = 3; i < 50; ++i ) ans[i] = ans[i-1] + ans[i-2];
    cin >> t;
    for ( i = 1; i <= t; ++i )
    {
        cin >> n;
        cout << "Scenario #" << i <<":" << endl;
        cout << ans[n] << endl << endl;
    }
    return 0>_<0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>