F(x)(デジタルdpの向上問題)(自分で思う)

HDU 4734 F(x) 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
この問題の大まかな意味は、関数F(x)=An*2 n-1+An-1*2 n-2+...+A 2*2+A 1*1.をあげることです.と2つの数aとbを数えます.F(v)<=F(a)(0<=v<=b)の間の個数を求めさせます.
考え方:この問題は私が最初から加算で作ったもので、それからこのようなことを知らないでTになったので、これはとても理解できません.それから大物たちが書いたブログを見て、加算は絶えず初期化しなければならないことに気づきました.あなたのaは絶えず変化しているので、F(a)も絶えず変化しているので、データを入力すると初期化しなければなりません.初期化を行わないと、前の検索をした可能性があり、次は前の状態を維持しているが、3次元配列dpを開くことはできない[20][4600][4600][4600].そうすればメモリが爆発する.この問題は減算に用いられ、2次元配列dpを定義する必要がある[20][4600].後の4600はF(a)−sumの値を格納するためのものであり、最初にF(a)の値をsumに格納し、減算を続け、sumが0より小さいかどうかを判断するだけで、0より小さいとF(v)>F(a)に相当するので、0を返すとよい.0より大きい場合は、1を返します.最後に、このような利点は、前の状態が次の状態に影響を及ぼす心配がなく、繰り返しの初期化操作を行わないことです.具体的なコードは以下の通りです.

#include
#include
#include
#include
using namespace std;
int fx;int l;
int a[20];
int dp[20][5500];
int dfs(int pos,int sum,bool lim){
     //       F(a)  
    if(pos<=0)//  pos=0,sum<0,  F（v）>F(a),         ，  ，    
        return sum>=0;
    if(sum<0)//sum<0          F(a),      0    
        return 0;
    if(!lim&&dp[pos][sum]!=-1)
        return dp[pos][sum];
    int up = lim ? a[pos] : 9;
    int ans = 0;
    for (int i = 0; i <= up;i++){
     
        int sum1 = i*(1<<(pos-1));//         dp          
        ans += dfs(pos - 1, sum-sum1, lim && i == up);
    }
    if(!lim)
        dp[pos][sum] = ans;
    return ans;
}
int solve(int x){
     
    int cnt = 1;
    while(l){
     
        int t = l % 10;
        l = l / 10;
        fx += cnt * t;
        cnt *= 2;
    }
    int pos = 0;
    while(x){
     
        a[++pos] = x % 10;
        x /= 10;
    }
    return dfs(pos, fx,  true);
}
int main(){
     
    int t;
    scanf("%d", &t);
    memset(dp, -1, sizeof dp);
    for(int i=1;i<=t;i++){
     
        
        int r;
        scanf("%d%d", &l, &r);
        fx = 0;
        printf("Case #%d: %d
",i, solve(r));
    }
}//  dp       

@浩然先辈の注意深い教えに感谢して、まだ分からないことがあることを望んで私を信じて、あるいはどこが悪いことを指摘することができます.皆さんの視聴率が長かったことに感謝します.