HDu 3709デジタルdp

デジタルdpは、さらなる理解があれば、テンプレートも最適化することができます.
題意:区間内の平衡数の個数を探し出して、いわゆる平衡数、この数字のある1位を支点にして、その他の両側の数字の大きさはモーメントの和を乗じて等しくて、つまり平衡数例えば4139で、3を支点にして4*2+1*1=9 and 9*1=9で、平衡数Sample Input 20 97604 24324 Sample Output 10897と称します
 

 1 #include<cstdio>

 2 #include<cstring>

 3 using namespace std;

 4 __int64 dp[19][19][2000];

 5 int digit[19];

 6 __int64 dfs(int p,int o,int s,bool e) {       //  ，    ，       ，     

 7     if (p==-1) return s==0;

 8     if(s<0)    return 0;

 9     if (!e &&dp[p][o][s]!=-1) return dp[p][o][s];

10     __int64 res = 0;

11     int u = e?digit[p]:9;

12     for (int d=0;d<=u;++d)

13     {

14         int ns=d*(p-o)+s;

15         res+=dfs(p-1,o,ns,e&&d==u);

16     }

17     return e?res:dp[p][o][s]=res;

18 }

19 __int64 solve(__int64 n)

20 {

21     int len=0;

22     while(n)

23     {

24         digit[len++]=n%10;

25         n/=10;

26     }

27     __int64 ans=0;

28     for(int i=0;i<len;i++)

29     {

30         ans+=dfs(len-1,i,0,1);

31     }

32     return ans-len+1;

33 }

34 int main()

35 {

36     int t;

37     __int64 n,m;

38     //freopen("1.in","r",stdin);

39     memset(dp,-1,sizeof(dp));

40     scanf("%d",&t);

41     while(t--)

42     {

43         scanf("%I64d%I64d",&n,&m);

44         printf("%I64d
",solve(m)-solve(n-1));

45     }

46 }