数位DP

题意:(hdu 4734)

  我们定义十进制数x的权值为f(x) = a(n)*2^(n-1)+a(n-1)*2(n-2)+...a(2)*2+a(1)*1,a(i)表示十进制数x中第i位的数字。

  题目给出a,b,求出0~b有多少个不大于f(a)的数

#include <stdio.h>
#include <string.h> int mx[];
int dp[][]; /*   <数位DP>     所谓数位DP就是基于考虑数字的每一位来转移的DP。     例如求比456小的数,可以这么考虑,         4 5 6         4  5 (0~6)         4 (0~4) (0~9)         (0~3) (0~9) (0~9)     然后我们就可以考虑用dp[len][pre]表示长度为len,以pre开头的符合条件的数的个数。     这样就可以得到转移方程了。   而对于这道题,我们可以用dp[len][pre]表示长度为len且权值不大于pre的数。   这道题用记忆化搜索,除边界条件外记录dp[len][pre]的值,下一次发现以前已经计算过了就可以直接return;   初值:dp[len][pre] = 0;      dfs(len, pre, flag)表示求长度为len,不超过pre的所有符合条件的值。其中flag是用来控制边界的。      dfs过程中当深搜的边界,发现len < 0,pre >=0 的时候就返回1.
*/ int dfs(int len, int pre, bool flag)
{
if ( len < ) return pre >=;
if ( pre < ) return ; if ( !flag && dp[len][pre] != -) return dp[len][pre]; int end = flag?mx[len]:;
int ans = ;
int i;
for( i = ; i <= end; i++)
{
ans += dfs(len-, pre- i*(<<len), flag&&i==end);
} if( !flag )dp[len][pre] = ans;
return ans;
} int f(int x)
{
int ans = ;
int tmp = ; while( x )
{
ans += (x%)*tmp;
tmp = tmp*;
x = x/;
} return ans;
} int cal(int a, int b)
{
int tmp = ; while( b )
{
mx[ tmp++ ]= b%;
b = b/;
}
return dfs(tmp - , f(a), true );
} int main()
{
int t;
int a,b;
scanf("%d", &t);
memset(dp, 0xff, sizeof(dp));
for(int i = ; i <= t; i++ )
{
scanf("%d%d",&a, &b);
printf("Case #%d: %d\n", i, cal(a,b));
}
return ;
}
上一篇:springday02-go4


下一篇:数位DP之奥义