hdu 3709（数位dp）

题意：给出x，y，求出x到y这个区间的平衡数个数。平衡数定义如题：http://acm.hdu.edu.cn/showproblem.php?pid=3709

思路：数位dp，记忆化搜索，dp[pos][rol][pre],pos表示当前位位置，rol表示轴的位置，pre表示当前状态下的权值大小。当pos=-1时表示数位处理完毕，检查结果并返回。当pre<0时返回函数。

limit表示是否有上限。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define LL __int64
 8 LL dp[20][20][2005];
 9 int bit[20];
10 LL dfs(int pos,int rol,int pre,bool limit){
11     //cout<<pos<<" "<<pre<<endl;
12     if(pos<0) return pre==0;
13     if(pre<0) return 0;
14     if(!limit&&dp[pos][rol][pre]!=-1)return dp[pos][rol][pre];
15     int end=limit?bit[pos]:9;
16     LL sum=0;
17     for(int i=0;i<=end;i++){
18         int t=pre+i*(pos-rol);
19         sum+=dfs(pos-1,rol,t,limit&&(i==end));
20     }
21     if(!limit)
22     dp[pos][rol][pre]=sum;
23     return sum;
24 }
25 LL slove(LL x){
26     int pos=0;
27     //if(x<0)return 0;
28     memset(dp,-1,sizeof(dp));
29     while(x){
30         bit[pos++]=x%10;
31         x/=10;
32     }
33     //cout<<x<<" "<<bit[0]<<endl;
34     LL sum=0;
35     for(int i=0;i<pos;i++){
36         sum+=dfs(pos-1,i,0,true);
37     }
38     //cout<<sum<<endl;
39     return sum-pos+1;
40 }
41 int main(){
42     int ca;
43     scanf("%d",&ca);
44     while(ca--){
45         LL x,y;
46         scanf("%I64d%I64d",&x,&y);
47         printf("%I64d\n",slove(y)-slove(x-1));
48     }
49     return 0;
50 }