数位DP：SPOJ KPSUM

KPSUM - The Sum

　　One of your friends wrote numbers 1, 2, 3, ..., N on the sheet of paper. After that he placed signs + and - between every pair of adjacent digits alternately. Now he wants to find the value of the expression he has made. Help him.

　　For example, if N=12 then +1 -2 +3 -4 +5 -6 +7 -8 +9 -1+0 -1+1 -1+2 = 5

Input

　　Each line contains one integer number N (1≤ N ≤ 1015). Last line contains 0 and shouldn't be processed. Number of lines in the input does not exceed 40.

Output

　　For every line in the input write the answer on a separate line.

Example

Input:
12
0

Output:
5

　　数位DP，表示一开始就打错了，然后乱改了一天，终于改对了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 long long Quick_pow(long long a,int k){
 6     long long ret=1;
 7     while(k){if(k&1)ret*=a;a=a*a;k>>=1;}
 8     return ret;
 9 }
10 
11 long long Query(long long sum,int lena,int lenb){
12     if(lena%2){
13         if(lenb%2)
14             return sum*Quick_pow(10,lenb)+45*Quick_pow(10,lenb-1);
15         else
16             return 5*Quick_pow(10,lenb-1);    
17     }
18     else{
19         if(lenb%2)
20             return 5*Quick_pow(10,lenb-1);
21         else
22             return sum*Quick_pow(10,lenb);    
23     }
24 }
25 int st[20],cnt;
26 int me[15]={0,1,-1,2,-2,3,-3,4,-4,5,-5};
27 long long Calc(long long a,int b){
28     if(a==0)return me[b]; 
29     int flag=-1;
30     long long ret=0;
31     for(int i=0;i<=b;i++){
32         long long x=a*10+i;cnt=0;
33         while(x){st[++cnt]=x%10;x/=10;}
34         while(cnt){
35             ret+=flag*st[cnt--];
36             flag=-flag;
37         }
38     }
39     return ret;
40 }
41 int num[25],tot;
42 long long mem[25]; 
43 int main(){
44     mem[1]=5;
45     for(int i=2;i<=15;i++){
46         for(int j=1;j<=9;j++)
47             mem[i]+=Query(-j,1,i-1);
48         mem[i]+=mem[i-1];
49     }
50     
51     long long n;
52     while(~scanf("%lld",&n)&&n){
53         long long ret=0,x=n,sum=0;tot=0;
54         while(x){num[++tot]=x%10;x/=10;}
55         for(int i=tot;i>1;i--){
56             if(!num[i])continue;
57             if(i!=tot)ret+=Query(sum,tot-i+1,i-1);
58             else ret+=mem[i-1];
59             for(int j=1;j<num[i];j++)
60                 ret+=Query(sum+Quick_pow(-1,tot-i+1)*j,tot-i+1,i-1);
61              sum+=Quick_pow(-1,tot-i+1)*num[i];
62         }
63         ret+=Calc(n/10,n%10);
64         printf("%lld
",ret);
65     }
66     return 0;
67 }

尽最大的努力，做最好的自己！