HDU 4734 - F(x)


http://acm.hdu.edu.cn/showproblem.php?pid=4734
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



https://blog.csdn.net/wust_zzwh/article/details/52100392
题目给了个f(x)的定义:F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1,Ai是十进制数位,然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。
常规想:这个f(x)计算就和数位计算是一样的,就是加了权值,所以dp[pos][sum],这状态是基本的。a是题目给定的,f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值,那就是dp[10][4600][4600],这显然不合法。
这个时候就要用减法了,dp[pos][sum],sum不是存当前枚举的数的前缀和(加权的),而是枚举到当前pos位,后面还需要凑sum的权值和的个数,
也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值,那么最后枚举完所有位 sum>=0时就是满足的,后面的位数凑足sum位就可以了。
仔细想想这个状态是与f(a)无关的(新手似乎很难理解),一个状态只有在sum>=0时才满足,如果我们按常规的思想求f(i)的话,那么最后sum>=f(a)才是满足的条件。
int dp[12][N];
int f(int x)
{
    if(x==0) return 0;
    int ans=f(x/10);
    return ans*2+(x%10);
}
int all;
int a[12];
int dfs(int pos,int sum,bool limit)
{
    if(pos==-1) {return sum<=all;}
    if(sum>all) return 0;
    if(!limit && dp[pos][all-sum]!=-1) return dp[pos][all-sum];
    int up=limit ? a[pos] : 9;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        ans+=dfs(pos-1,sum+i*(1<<pos),limit && i==a[pos]);
    }
    if(!limit) dp[pos][all-sum]=ans;
    return ans;
}
int solve(int x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,true);
}
int main()
{
    int a,ri;
    int T_T;
    int kase=1;
    scanf("%d",&T_T);
    memset(dp,-1,sizeof dp);
    while(T_T--)
    {
        scanf("%d%d",&a,&ri);
        all=f(a);
        printf("Case #%d: %d\n",kase++,solve(ri));
    }
    return 0;
}
https://blog.csdn.net/feng_zhiyu/article/details/78796133
dp[i][j]表示i位数比j小的数的个数, 另外注意状态转移方程: 
dp[i][j]+=dp[i-1][j-k*(1<<(i-1))];
https://blog.csdn.net/deepseazbw/article/details/78247376
http://www.voidcn.com/article/p-kjzblhod-bmt.html
https://github.com/AplusB/ACEveryDay/blob/master/QAsQ/Blog/HDU%204734%20F(x).md
常规想:这个f(x)计算就和数位计算是一样的,就是加了权值,所以dp[pos][sum],这状态是基本的。a是题目给定的,f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值,那就是dp[10][4600][4600],这显然不合法。
这个时候就要用减法了,dp[pos][sum],sum不是存当前枚举的数的前缀和(加权的),而是枚举到当前pos位,后面还需要凑sum的权值和的个数,
也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值,那么最后枚举完所有位 sum>=0时就是满足的,后面的位数凑足sum位就可以了。
仔细想想这个状态是与f(a)无关的(新手似乎很难理解),一个状态只有在sum>=0时才满足,如果我们按常规的思想求f(i)的话,那么最后sum>=f(a)才是满足的条件。
  1. const int N =1e4+5;
  2. int dp[12][N];
  3. int all;
  4. int a[12];
  5. int f(int x)
  6. {
  7. if(x==0)
  8. return 0;
  9. int ans=f(x/10);
  10. return ans*2+(x%10);
  11. }
  12. int dfs(int pos,int sum,bool limit)
  13. {
  14. if(pos==-1) return sum<=all;
  15. if(sum>all) return 0;
  16. if(!limit&&dp[pos][all-sum]!=-1) return dp[pos][all-sum];
  17. int up=limit?a[pos]:9;
  18. int ans=0;
  19. for(int i=0;i<=up;i++)
  20. ans+=dfs(pos-1,sum+i*(1<<pos),limit&&i==a[pos]);
  21. if(!limit) dp[pos][all-sum]=ans;
  22. return ans;
  23. }
  24. int solve(int x)
  25. {
  26. int pos=0;
  27. while(x)
  28. {
  29. a[pos++]=x%10;
  30. x/=10;
  31. }
  32. return dfs(pos-1,0,true);
  33. }
  34. int main()
  35. {
  36. int a,ri,icase,kase=1;
  37. scanf("%d",&icase);
  38. while(icase--)
  39. {
  40. scanf("%d%d",&a,&ri);
  41. all=f(a);
  42. printf("Case #%d: %d\n",kase++,solve(ri)-0);
  43. }
  44. return 0;
  45. }


http://semon0x29a.cn/2018/09/12/HDU-4734/
一开始我的做法是基于dp[u][prefix]的数位dp, 第一维表示当前数位, 第二维表示前部的级数和, 但是数据组数太多,会TLE。
于是考虑将第二维倒过来,变为dp[u][F(A)prefix], 这样就可以复用前面数据计算过的dp数组, 于是O(Accepted)

int n, a, b;
int v[12];
int dp[12][9300];

int dfs(int u, bool limits, int pre) {
    if (pre < 0) return 0;
    if (u == -1) return 1;
    if (!limits && dp[u][pre] != -1) {
        return dp[u][pre];
    }
    int res = 0, top = limits ? v[u] : 9;
    for (int i = 0; i <= top; i++) {
        res += dfs(u - 1, limits && (i == top), pre - i * (1 << u));
    }
    if (!limits) dp[u][pre] = res;
    return res;
}

int calc() {
    if (b == 0) return 1;
    for (n = 0; b > 0; b /= 10) {
        v[n++] = b % 10;
    }
    int sum = 0, mul = 1;
    while (a > 0) {
        sum += (a % 10) * mul;
        mul <<= 1;
        a /= 10;
    }
    return dfs(n - 1, true, sum);
}

http://vawait.com/2013/09/hdu-4734/
f[i][j]表示有i位数随意填F()值不超过j的方案数。
void init()
{
    b[1] = 1;
    rep(i,2,12) b[i] = b[i-1] * 2;
    clr(f,0);
    f[0][0] = 1;
    rep(i,1,10)
        rep(j,0,5000)
            rep(k,0,9) if ( k * b[i] <= j ) f[i][j] += f[i-1][j-k*b[i]];
    rep(i,0,10)
        rep(j,1,5000) f[i][j] += f[i][j-1];
}
int calc(int k)
{
    s = 0;
    while ( k ) {
        a[++s] = k % 10;
        k /= 10;
    }
    int sum=0;
    rep(i,1,s) sum += a[i] * b[i];
    return sum;
}
void dfs(int t,int s)
{
    int k;
    if ( s < 1 || t > m ) return;
    rep(i,0,a[s] - 1) {
        k = t + i * b[s];
        if ( k > m ) continue;
        ans += f[s-1][m-k];
    }
    dfs( t + a[s] * b[s], s - 1);
}

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts