题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4734
Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
For each test case, there are two
numbers A and B (0 <= A,B < 109)
without quotes. The t is the case number starting from 1. Then output the
answer.
题意：
给出T组数据，对于每组数据有A,B；
假设数字x有n位:(AnAn-1An-2 ... A2A1)，那么定义数字x的权重计算函数为F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1；
现在要求[0,B]之间，有多少个数字的权重不大于F(A).
题解：
刚开始一眼看到这题，算了一下 F(999999999) = 4599，也不是很大，
就感觉挺简单的，想着dp[pos][weight]不就完事了，weight记录从len到pos位上数字累计的权重；
写出来交了一发，TLE，感觉就有点奇怪，翻了翻网上的题解，说是不能是dp[pos][weight]，要是dp[pos][F(A) - weight]才行；
也就是说，新定义dp[pos][comp]，comp代表剩下的从第pos位到第1位，累加起来的权重，不能超过comp；
这是为什么呢？原因其实很简单：
我们定义dp[pos][weight]的话，显然我们这T组数据……
每组数据只要B有变化，由于weight是从最高位往下累加权重，它跟B有密切关系（B的长度len即为最高位），那么dp数组就要重新memset(dp,-1,sizeof(dp))，这样才不会出错；
那么我们如果是dp[pos][comp]呢，comp代表从第1位到第pos位最多还能累加起多少权重，那么它就和B没什么关系，我们就不需要在输入每组数据后都重新将DP数组全部重置为-1。
AC代码：
#include<bits/stdc++.h>
using namespace std;
int dig[];
int dp[][];
int A,B;
int pow2[]; int F(int x)
{
int cnt=;
int ret=;
while(x)
{
ret+=(x%)<<cnt;
x/=;
cnt++;
}
return ret;
} int dfs(int pos,int comp,bool limit)
{
if(pos==) return comp>=;
if(!limit && dp[pos][comp]!=-) return dp[pos][comp]; int up=limit?dig[pos]:;
int ans=;
for(int i=;i<=up;i++)
{
int new_comp=comp-i*pow2[pos-];
if(new_comp<) continue;
ans+=dfs(pos-,new_comp,limit && i==up);
} if(!limit) dp[pos][comp]=ans;
return ans;
}
int solve(int x)
{
int len=;
while(x)
{
dig[++len]=x%;
x/=;
}
return dfs(len,F(A),);
} int main()
{
pow2[]=;
for(int i=;i<=;i++) pow2[i]=pow2[i-]*; int t;
scanf("%d",&t);
memset(dp,-,sizeof(dp));
for(int kase=;kase<=t;kase++)
{
scanf("%d%d",&A,&B);
printf("Case #%d: %d\n",kase,solve(B));
}
}