Lightoj1032——Fast Bit Calculations（數位dp）

A bit is a binary digit, taking a logical value of either 1 or 0 (also referred to as “true” or “false” respectively). And every decimal number has a binary representation which is actually a series of bits. If a bit of a number is 1 and its next bit is also 1 then we can say that the number has a 1 adjacent bit. And you have to find out how many times this scenario occurs for all numbers up to N.

Examples:

Number         Binary          Adjacent Bits

     12                    1100                        1
     15                    1111                        3
     27                    11011                      2
           

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer N (0 ≤ N < 231).

Output

For each test case, print the case number and the summation of all adjacent bits from 0 to N.

Sample Input

7

6

15

20

21

22

2147483647

Output for Sample Input

Case 1: 0

Case 2: 2

Case 3: 12

Case 4: 13

Case 5: 13

Case 6: 14

Case 7: 16106127360

轉換成二進制dp

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <cmath>
#include <map>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 10000005
#define Mod 10001
using namespace std;
int dight[];
long long dp[][][];
long long dfs(int pos,int s,bool limit,int sum)
{
    if(pos==)
        return sum;
    if(!limit&&dp[pos][s][sum]!=-)
        return dp[pos][s][sum];
    int end;
    long long ret=;
    if(limit)
        end=dight[pos];
    else
        end=;
    for(int d=; d<=end; ++d)
    {
        if(s)
        {
            if(d==)
                ret+=dfs(pos-,,limit&&d==end,sum+);
            else
                ret+=dfs(pos-,,limit&&d==end,sum);
        }
        else
        {
            if(d==)
                ret+=dfs(pos-,,limit&&d==end,sum);
            else
                ret+=dfs(pos-,,limit&&d==end,sum);
        }
    }
    if(!limit)
        dp[pos][s][sum]=ret;
    return ret;
}
long long solve(long long a)
{
    memset(dight,,sizeof(dight));
    int cnt=;
    while(a!=)
    {
        dight[cnt++]=a%;
        a/=;
    }
    return dfs(cnt-,,,);
}
int main()
{
    memset(dp,-,sizeof(dp));
    int t,cnt=;
    scanf("%d",&t);
    while(t--)
    {
        long long x;
        scanf("%lld",&x);
        printf("Case %d: %lld\n",cnt++,solve(x));
    }
    return ;
}