URAL - 1012 DP+高精度

和1009一个意思...就是范围大了...要用高精度...用JAVA大数应该方便些....这里的turn是调整高精度数组为每一位都只有一位数并且更新长度...

Program:

#include<iostream>
#include<stdio.h>
using namespace std;
struct pp
{
    int a[200],len;      
}dp[200];
int n,k,i,j;
void turn(int k)
{
    int p=1; 
    for (p=1;p<=dp[k].len;p++)
    {
       dp[k].a[p+1]+=dp[k].a[p]/10;
       dp[k].a[p]%=10;     
    }    
    while (dp[k].a[dp[k].len+1]>0) 
    {
       dp[k].len++;    
       dp[k].a[dp[k].len+1]=dp[k].a[dp[k].len]/10;
       dp[k].a[dp[k].len]%=10;  
    }
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {     
         memset(dp,0,sizeof(dp)); 
         dp[1].len=1; dp[1].a[1]=k-1;  turn(1);
         dp[2].len=1; dp[2].a[1]=(k-1)*k; turn(2);
         for (i=3;i<=n;i++)
         {
       //     dp[i]=(k-1)*(dp[i-1]+dp[i-2]);
             dp[i].len=dp[i-1].len;
             for (j=1;j<=dp[i-1].len;j++)
               dp[i].a[j]=dp[i-1].a[j]+dp[i-2].a[j]; 
             turn(i);
             for (j=1;j<=dp[i].len;j++) dp[i].a[j]*=k-1;
             turn(i);             
         }
         for (i=dp[n].len;i>=1;i--) printf("%d",dp[n].a[i]);
         printf("\n");                        
    }
    return 0;   
}