HDU 4734 F(x) （数位dp+ 记忆化）

时间：2015-03-26 15:01:02 收藏：0 阅读：243

Problem Description

For a decimal number x with n digits (A_nA_n-1A_n-2 ... A₂A₁), we define its weight as F(x) = A_n * 2^n-1 + A_n-1 * 2^n-2 + ... + A₂ * 2 + A₁ * 1. Now you are given two numbers A and B, please calculate how many numbers are there between 0 and B, inclusive, whose weight is no more than F(A).

Input

The first line has a number T (T <= 10000) , indicating the number of test cases.
For each test case, there are two numbers A and B (0 <= A,B < 10⁹)

Output

For every case,you should output "Case #t: " at first, without quotes. The t is the case number starting from 1. Then output the answer.

Sample Input

Sample Output

Case #1: 1
Case #2: 2
Case #3: 13

参考博客：http://www.myexception.cn/other/1405915.html

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>


#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
typedef __int64 ll;

#define fre(i,a,b)  for(i = a; i <b; i++)
#define free(i,b,a) for(i = b; i >= a;i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define ssf(n)      scanf("%s", n)
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf          printf
#define bug         pf("Hi\n")

using namespace std;

#define INF 0x3f3f3f3f
#define N  200000

int dp[20][N];
int a[30],k;

int F(int x)
{
	k=0;
	int temp=0;
	while(x)
	{
		temp+=(x%10)*(1<<k);
		k++;
		x/=10;
	}
    return temp;
}

void hello(int x)
{
	k=0;
	while(x)
	{
		a[k++]=x%10;
		x/=10;
	}
}

int dfs(int pos,int va,int flag)   //dp[i][j] 表示第i位小于等于va有多少种情况
{                                 //flag记录是不是第i位是不是可以从0~9
     if(pos==-1) return va>=0;

	 if(va<0) return 0;

     if(!flag&&dp[pos][va]!=-1)
		return dp[pos][va];

     int ri=flag ? a[pos]:9;
     int i;

     int temp=0;

     fre(i,0,ri+1)
     {
     	temp+=dfs(pos-1,va-i*(1<<pos),flag&&(i==ri));
     }

    if(!flag) dp[pos][va]=temp;

    return temp;
}

int main()
{
	int i,t,j,le,ri,ca=0;
	sf(t);
	mem(dp,-1);

	while(t--)
	{
		sff(le,ri);
		le=F(le);


		hello(ri);

        pf("Case #%d: ",++ca);
		pf("%d\n",dfs(k-1,le,1));
	}

	return 0;
}

原文：http://blog.csdn.net/u014737310/article/details/44648175