首页 > 代码库 > lightoj1032_数位dp
lightoj1032_数位dp
题目链接：http://lightoj.com/volume_showproblem.php?problem=1032
| PDF (English) | Statistics | Forum |
| Time Limit: 2 second(s) | Memory Limit: 32 MB |
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 | Output for Sample Input |
7 0 6 15 20 21 22 2147483647 | Case 1: 0 Case 2: 2 Case 3: 12 Case 4: 13 Case 5: 13 Case 6: 14 Case 7: 16106127360 |
思路:dp[len][pre][con]表示到当前位置，前一位是pre时，前面有多少个11的答案是多少
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <set>11 #include <map>12 using namespace std;13 #define INF 0x3f3f3f3f14 typedef long long LL;15 16 int bit[50];17 LL dp[50][2][50];18 LL dfs(int len, int pre, int con, int flag)19 {20 if(len == 0)21 return con;22 if(dp[len][pre][con] >= 0 && flag)23 return dp[len][pre][con];24 int te = flag ? 1 : bit[len];25 LL sum = 0;26 for(int i = 0; i <= te; i++)27 {28 if(pre == 1 && i == 1)29 sum += dfs(len-1, i, con+1, flag || i < te);30 else31 sum += dfs(len-1, i, con, flag || i < te);32 }33 if(flag)34 dp[len][pre][con] = sum;35 return sum;36 }37 int main()38 {39 int t, n;40 scanf("%d", &t);41 memset(dp, -1, sizeof(dp));42 for(int ca = 1; ca <= t; ca++)43 {44 scanf("%d", &n);45 int len = 0;46 while(n)47 {48 bit[++len] = n % 2;49 n >>= 1;50 }51 printf("Case %d: %lld\n", ca, dfs(len, 0, 0, 0));52 }53 return 0;54 }
lightoj1032_数位dp