LightOJ 1032 - Fast Bit Calculations 数位DP

http://www.lightoj.com/volume_showproblem.php?problem=1032

题意：问1~N二进制下连续两个1的个数

思路：数位DP，dp[i][j][k]代表第i位为j，前面已有k个1的个数。

/** @Date    : 2016-12-17-13.51

  * @Author  : Lweleth (SoungEarlf@gmail.com)

  * @Link    : https://github.com/

  * @Version :

  */

#include<bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset(x, -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int bit[50];

LL dp[50][2][50];

LL dfs(int pos, int pre, int cnt, int ise)

{

    if(pos <= 0)

        return cnt;

    if(!ise && dp[pos][pre][cnt]!=-1)

        return dp[pos][pre][cnt];

    LL ans = 0;

    int len = ise?bit[pos]:1;

    for(int i = 0; i <= len; i++)

    {

        if(pre && i)

            ans += dfs(pos - 1, i, cnt + 1, ise && i == len);

        else

            ans += dfs(pos - 1, i, cnt, ise && i== len);

    }

    if(!ise)

        dp[pos][pre][cnt] = ans;

    return ans;

}

LL sol(int n)

{

    int len = 0;

    MMG(dp);

    while(n)

    {

        bit[++len] = n % 2;

        n /= 2;

    }

    return dfs(len, 0, 0, 1);

}

int main()

{

    int T;

    int cnt = 0;

    cin >> T;

    while(T--)

    {

        int n;

        scanf("%d", &n);

        printf("Case %d: %lld\n", ++cnt, sol(n));

    }

    return 0;

}

巴特西

LightOJ 1032 - Fast Bit Calculations 数位DP

最新文章

热门文章