通過(guò)這相似的三道題體會(huì)到了“量變引起質(zhì)變”的道理。第一題數(shù)據(jù)規(guī)模很小，當(dāng)然可以DP，但是搜索就足夠了；第二題規(guī)模大了不少，高精度是必須的，同時(shí)需要用動(dòng)態(tài)規(guī)劃，遞推和記憶化兩種形式，我一直偏愛(ài)記憶化，選擇了記憶化搜索；第三題規(guī)模繼續(xù)增大，為了節(jié)省空間，高精度用到了壓位存儲(chǔ)，同時(shí)記憶化不再可行！因?yàn)闀?huì)造成棧崩潰！改用遞推。
以下是我的代碼：
#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 閱讀(435)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：遞推/遞歸