通过这相似的三道题体会到了“量变引起质变”的道理。第一题数据规模很小，当然可以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 阅读(414)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：递推/递归