hdu 4734 F(x)

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=4734

Solution

注意到f(x)不超过 4600

容易想到定义f[pos][sum]为选了前pos位，和为sum且不超过f(a)的方案数

但是这样计算对于每组数据都必须重新计算一遍 f

使得复杂度为 $O((T+len^2)sum)$

我们考虑定义 f[pos][sum]为选了前pos位，还剩下sum能选的方案数

这样的复杂度为 $O(len^2sum)$

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 10
#define maxm 4600
using namespace std;

int n, m, T;

int f[maxn][maxm], d[maxn], len; 
int dfs(int pos, bool limit, int sum) {
    if (!pos) return sum >= 0;
    if (sum < 0) return 0; 
    if (!limit && ~f[pos][sum]) return f[pos][sum];
    int up = limit ? d[pos] : 9, ans = 0; 
    for (int i = 0; i <= up; ++i)
        ans += dfs(pos - 1, limit && i == d[pos], sum - i * (1 << pos - 1)); 
    if (!limit) f[pos][sum] = ans;
    return ans;
}

int calc(int x) {
    int s = 0, l = 0; 
    while (x) { ++l;
        s += x % 10 * 1 << l - 1;
        x /= 10; 
    } return s;
} 

int solve(int x) { len = 0;
    while (x) {
        d[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, 1, calc(m)); 
}

int icase; 
void work() {
    cin >> m >> n; //memset(f, -1, sizeof f); 
    printf("Case #%d: %d\n", ++icase, solve(n));
} 

int main() {
    cin >> T; memset(f, -1, sizeof f); 
    while (T--) work(); 
    return 0;
}