FZU 2070 - Beautiful number 數位DP..

             題意:

                       一個數前len/2個數字之和和後(len+1)/2數字之和相同稱為Beautiful number..現在問A~B有多少個Beautiful number。

             題解:

                      典型的數位dp...我寫數位dp總是寫得很蛋疼..一定是方法有問題...

                      狀态是這樣的dp[L][D][M]代表長度為L的數.第一個數字為D.數位之和為M的個數...

                      主要是構造個數的時候有些麻煩...

Program:

#include<iostream>      
#include<algorithm>      
#include<stdio.h>      
#include<string.h>    
#include<time.h>   
#include<map>   
#include<math.h>      
#include<queue>      
#define MAXN 100005
#define MAXM 500005 
#define oo 1000000007      
#define ll long long      
#define MOD 1000000  
using namespace std; 
ll dp[22][12][185];
void PreWork()
{
      int t,x,p,i;
      memset(dp,0,sizeof(dp));
      dp[0][0][0]=1;
      for (t=1;t<=18;t++)
         for (x=0;x<10;x++)
            for (p=0;p<=170;p++)
              for (i=0;i<10;i++)
                dp[t][x][p+x]+=dp[t-1][i][p];              
} 
ll count(ll x)
{
      ll sum=0;
      int len,L,i,j,p,h,t=0;   
      char s[22]; 
      if (x<10) return 0;
      sprintf(s+1,"%I64d",x),len=strlen(s+1);
      L=len/2;  
      for (h=len;h>=1;h--)
      {
              if (!L) L=(len+1)/2;
              if (h>(len+1)/2)
              {
                     if (h==len) i=1;
                            else i=0;
                     for (;i<s[len-h+1]-'0';i++)  
                         for (p=0;p<=170-t;p++)
                            for (j=0;j<10;j++)
                               sum+=dp[L][i][p]*dp[(len+1)/2][j][p+t];
                     t+=s[len-h+1]-'0';
                     L--;
              }else 
              {
                     for (i=0;i<s[len-h+1]-'0';i++) sum+=dp[L][i][t];
                     t-=s[len-h+1]-'0';
                     if (t<0) break;
                     L--;
              }
      }     
      if (!t) sum++;
      for (L=len-1;L>=1;L--)
         for (i=1;i<10;i++)
            for (x=0;x<10;x++)
               for (p=0;p<=170;p++)
                  sum+=dp[L/2][i][p]*dp[(L+1)/2][x][p]; 
      return sum;
}
int main()     
{            
      int C,cases;
      ll A,B; 
      PreWork();
      scanf("%d",&C);
      for (cases=1;cases<=C;cases++)
      {
               scanf("%I64d%I64d",&A,&B);
               printf("%I64d\n",count(B)-count(A-1));
      }
      return 0;    
}