Posted on 2009-03-13 17:13
Hero 閱讀(108)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
代碼如詩(shī)－－ACM
1 //1044 Accepted 15 76 401 C++
2 //簡(jiǎn)單遞推
3
4 #include <stdio.h>
5 #include <stdlib.h>
6 #include <string.h>
7
8 __int64 dp[100][2] ;
9 int inn, ink ;
10
11 int main()
12 {
13 while( scanf( "%d %d", &inn, &ink ) != EOF )
14 {
15 dp[1][0] = 0 ; dp[1][1] = ink - 1 ;
16
17 for( int i=2; i<=inn; i++ )
18 {
19 dp[i][0] = dp[i-1][1] ;
20 dp[i][1] = ( dp[i-1][0]+dp[i-1][1] ) * (ink-1) ;
21 }
22
23 printf( "%I64d\n", dp[inn][0]+dp[inn][1] ) ;
24 }
25 return 0 ;
26 }