F(x) Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8478 Accepted Submission(s): 3339
Problem Description
For a decimal number x with n digits (AnAn-1An-2 ... A2A1), we define its weight as F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 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 < 109)
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
3
0 100
1 10
5 100
Sample Output
Case #1: 1 Case #2: 2 Case #3: 13
传送门
题意： 我们定义十进制数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)的数。
对于这道题，我们可以用dp[len][ans]表示长度为len且权值不大于ans的数。 这道题用记忆化搜索，除边界条件外记录dp[len][ans]的值，下一次发现以前已经计算过了就可以直接return；
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include<cmath> #define ll long long using namespace std; ll a[20]; ll dp[20][5000]; ll m,n; int dfs(int len,int ans,int flag) { if(len==0) return ans>=0; if(ans<0) return 0; int sum=0; if(!flag&&dp[len][ans]!=-1)return dp[len][ans]; int end=flag?a[len]:9; for(int i=0; i<=end; i++) { sum+=dfs(len-1,ans-i*(pow(2,len-1)),flag&&i==end); // i*(pow(2,len-1) 这里很多人 写的是 1<<len 等价于 pow(2,len) // 但是严格按照题意的话 应该是 An*2^n-1; } if(!flag)dp[len][ans]=sum; return sum; } ll f(ll x) { ll ans=0; ll len=1; while(x) { ans+=x%10*len; len*=2; x/=10; } return ans; } ll solve(ll x) { ll len=0; while(x) { a[++len]=x%10; x/=10; } ll ans=f(m); return dfs(len,ans,1); } int main() { int t; scanf("%d",&t); memset(dp,-1,sizeof(dp)); int tt=0; while(t--) { scanf("%lld%lld",&m,&n); printf("Case #%d: %d\n",++tt,solve(n)); } return 0; }
