首页 > 代码库 > uva 1350 - Pinary(dp+计数)

uva 1350 - Pinary(dp+计数)

题目链接:uva 1350 - Pinary

题目大意:给出n,输出第n给Pinary Number,Pinary Number为二进制数,并且没有连续两个1相连。

解题思路:dp[i]表示到第i位有dp[i]种,于是给定n,一层循环判断dp[i]n的话,就输出1,并且n减掉dp[i],注意输出0的时候,不能输出前导0.

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 50;
ll dp[N];

void init () {
    memset(dp, 0, sizeof(dp));
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= 40; i++)
        dp[i] = dp[i-1] + dp[i-2];
}

void solve (ll n) {
    bool flag = false;    

    for (int i = 40; i; i--) {
        if (n >= dp[i]) {
            printf("1");
            n -= dp[i];
            flag = true;
        } else if (flag)
            printf("0");
    }
    printf("\n");
}

int main () {
    init ();
    int cas;
    ll n;
    scanf("%d", &cas);
    for (int i = 0; i < cas; i++) {
        scanf("%lld", &n);
        solve(n);
    }
    return 0;
}