http://acm.hdu.edu.cn/showproblem.php?pid=4734
一般数位dp表示的是数的性质，这个题目也是一样，但是我们求出来的是一个函数的值，怎么把这个值转化成一类数，然后再用dp数字来表示这个数的性质呢?
这个我觉得挺麻烦的，很自然发现了这个f[x]并不是很大，最大应该就是10000左右，所以就可以放入数组里面表示
所以就有dp[pos][sum] 但是呢，这个是有问题的，因为如果你用sum来表示前缀和，那就无法进行记忆化，这个dp数组就会出现问题。
然后我就懵了，然后没忍住又去看了一下题解，题解说后面的那维不存前缀和sum，而是存ex-sum 表示前面以及有了sum后面还需要ex-sum这个的数的个数
然后这个就是对的了，至于为什么，你可以理解为我要求一类数，这类数有pos位，然后后面这类数的f(x)必须小于等于sum，这就是一种数的性质。
#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #include <iostream> #define inf 0x3f3f3f3f using namespace std; const int maxn = 1e5 + 10; typedef long long ll; int a[100]; int f(int x) { int pos = 0; int ans = 0; while(x) { ans += (x % 10)*(1 << pos); x /= 10; pos++; } return ans; } int ex; int dp[12][50000]; int dfs(int pos,int sum,bool limit) { if (pos == -1) return sum <= ex; if (sum > ex) return 0; if (!limit&&dp[pos][ex-sum] != -1) return dp[pos][ex-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 == up)); } if (!limit) dp[pos][ex-sum] = ans; return ans; } ll solve(ll x) { int pos = 0; while(x) { a[pos++] = x % 10; x /= 10; } return dfs(pos - 1, 0, 1); } int main() { int t; scanf("%d", &t); memset(dp, -1, sizeof(dp)); for(int cas=1;cas<=t;cas++) { int x, y; scanf("%d%d", &x, &y); ex = f(x); int ans = solve(y); printf("Case #%d: %d\n",cas, ans); } return 0; }