URAL - 1013 DP+高精度+滚动数组

同URAL - 1012 ..范围更大了...时间不是问题..主要是会爆内存...只要用滚动数组来存就可以了..因为每次做递推的时候只要用到 k 、k-1 和 k-2..每次dp[3]记录最新更新的值..昨晚后 dp[1]=dp[2] .. dp[2]=dp[3]..就滚过去了...下次再更新到dp[3].....

program:

#include<iostream>  
#include<stdio.h>  
using namespace std;  
struct pp  
{  
    int a[2000],len;        
}dp[4];  
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++)  
         {  
             memset(dp[3].a,0,sizeof(dp[3].a)); 
             dp[3].len=dp[2].len;  
             for (j=1;j<=dp[2].len;j++)  
               dp[3].a[j]=dp[2].a[j]+dp[1].a[j];   
             turn(3);  
             for (j=1;j<=dp[3].len;j++) dp[3].a[j]*=k-1;  
             turn(3);   
             dp[1]=dp[2]; dp[2]=dp[3];            
         }  
         for (i=dp[2].len;i>=1;i--) printf("%d",dp[2].a[i]);  
         printf("\n");                          
    }  
    return 0;     
}