點(diǎn)擊打開(kāi)題目

注意：dp[pos][sum]，sum不是存當(dāng)前枚舉的數(shù)的前綴和(加權(quán)的)，而是枚舉到當(dāng)前pos

位，后面還需要湊sum的權(quán)值和的個(gè)數(shù)

代碼：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 10;const int maxm = 1e4+5;int dp[maxn][maxm], a[maxn], A, B, sumA;int dfs(int pos, int sum, int limit){    if(pos == -1) return sum <= sumA;    if(sum > sumA) return 0;    if(!limit && dp[pos][sumA-sum] != -1) return dp[pos][sumA-sum];    int up = limit ? a[pos] : 9;    int tmp = 0;    for(int i = 0; i <= up; i++)        tmp += dfs(pos-1, sum+i*(1<<pos), limit && a[pos] == i);    if(!limit) dp[pos][sumA-sum] = tmp;    return tmp;}int solve(){    int pos = 0, p = 1;    sumA = 0;    while(A)    {        sumA += A%10*p;        p *= 2;        A /= 10;    }    while(B)    {        a[pos++] = B%10;        B /= 10;    }    return dfs(pos-1, 0, 1);}int main(void){    int ca = 1, t;    memset(dp, -1, sizeof(dp));    cin >> t;    while(t--)    {        scanf("%d%d", &A, &B);        PRintf("Case #%d: %d/n", ca++, solve());    }    return 0;}
F(x)
Time Limit: 1000/500 MS (java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5013    Accepted Submission(s): 1866Problem DescriptionFor 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). InputThe 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) OutputFor 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
30 1001 105 100 Sample Output
Case #1: 1Case #2: 2Case #3: 13 Source2013 ACM/ICPC Asia Regional Chengdu Online