通過這相似的三道題體會到了“量變引起質變”的道理。第一題數據規模很小，當然可以DP，但是搜索就足夠了；第二題規模大了不少，高精度是必須的，同時需要用動態規劃，遞推和記憶化兩種形式，我一直偏愛記憶化，選擇了記憶化搜索；第三題規模繼續增大，為了節省空間，高精度用到了壓位存儲，同時記憶化不再可行！因為會造成棧崩潰！改用遞推。
以下是我的代碼：
#include<stdio.h>
#include<string.h>
#define max_digit 300
#define maxn 1801
typedef struct
{
long n,s[max_digit];
}bign;
long n,k;
bign d[maxn][2];
void Add(bign &c,bign &a,bign &b)
{
memset(c.s,0,sizeof(c.s));
c.n=(a.n>b.n?a.n:b.n);
for(long i=0;i<c.n;i++)
{
c.s[i]+=a.s[i]+b.s[i];
if(c.s[i]>=100000000)
{
c.s[i+1]+=c.s[i]/100000000;
c.s[i]%=100000000;
}
}
if(c.s[c.n]) c.n++;
}
void Mul(bign &c,long t,bign &a)
{
memset(c.s,0,sizeof(c.s));
c.n=a.n;
for(long i=0;i<c.n;i++)
c.s[i]=t*a.s[i];
for(long i=0;i<c.n;i++)
if(c.s[i]>=100000000)
{
c.s[i+1]+=c.s[i]/100000000;
c.s[i]%=100000000;
}
if(c.s[c.n]) c.n++;
}
void Print(bign &a)
{
printf("%ld",a.s[a.n-1]);
for(long i=a.n-2;i>=0;i--)
printf("%08ld",a.s[i]);
}
int main()
{
scanf("%ld%ld",&n,&k);
d[n][1].n=1;d[n][1].s[0]=k;
d[n][0].n=1;d[n][0].s[0]=k-1;
for(long i=n-1;i>=1;i--)
{
if(i==1)
{
Mul(d[i][1],k-1,d[i+1][1]);
continue;
}
bign t;
Mul(t,k-1,d[i+1][1]);
Add(d[i][1],t,d[i+1][0]);
Mul(d[i][0],k-1,d[i+1][1]);
}
Print(d[1][1]);printf("\n");
return 0;
}
posted on 2010-09-10 21:51
lee1r 閱讀(436)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：遞推/遞歸