URAL 1012 K-based Numbers. Version 2（DP+高精度）

题意：与1009一样，不过这个题的数据范围变大。

思路：因为数据范围变大，所以要用大数模拟，用java也行，大数模拟也没什么不过变成二维再做就行了呗。当然也可以先把所有的都进行打表，不过要用三维了就。

 1 //URAL 1012
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 int a[185];
 9 int dp[185][201] ;
10 
11 int main()
12 {
13     int n, k ;
14     scanf("%d%d",&n,&k) ;
15     memset(dp,0,sizeof(dp)) ;
16     dp[1][200] = k-1 ;
17     dp[2][200] = k*(k-1) ;
18     for(int i = 3 ; i <= n ; i++)
19     {
20         memset(a,0,sizeof(a)) ;
21         for(int j = 200 ; j >= 0 ; j--)
22             a[j] = dp[i-1][j]+dp[i-2][j] ;
23         for(int j = 200 ; j >= 0 ; j--)
24         {
25             if(a[j] > 9)
26             {
27                 a[j-1] += a[j]/10 ;
28                 a[j] = a[j]%10 ;
29             }
30         }
31         for(int j = 200 ; j >= 0 ; j--)
32             dp[i][j] = a[j]*(k-1) ;
33         for(int j = 200 ; j >= 0 ; j--)
34         {
35             if(dp[i][j] > 9)
36             {
37                 dp[i][j-1] += dp[i][j]/10 ;
38                 dp[i][j] %= 10 ;
39             }
40         }
41     }
42     int i = 0 ;
43     while(dp[n][i] == 0) i++ ;
44     for( ; i <= 200 ; i++)
45         printf("%d",dp[n][i]) ;
46     printf("
") ;
47     return 0 ;
48 
49 }

View Code