作者在 2008-06-12 23:36:29 发布以下内容
dP+高精度
c[i]=c[i-1]+2*[i-2];
这个最优的东西我是很难自己想到的,我是看报告过的。
这个转移方程,是在太痛苦了。
#include <iostream>
using namespace std;
int c[250][100]={0};
void high_int(int m,int n,int k)
{
int i, index=0;
for(i=99;i>=0;i--)
{
c[m][i]=(c[n][i]+c[k][i]+c[k][i]+index)%10;
index=(c[n][i]+c[k][i]+c[k][i]+index)/10;
}
return;
}
void get_list()
{
c[0][99]=1;
c[1][99]=1;
for(int i=2;i<=250;i++)
{
high_int(i,i-1,i-2);
}
return ;
}
int main()
{
get_list();
int n;
while(cin >>n)
{
int i;
for( i=0;i<100;i++)
{
if(c[n][i]!=0)
break;
}
for(i;i<100;i++)
cout<<c[n][i];
cout<<endl;
}
return 0;
}
using namespace std;
int c[250][100]={0};
void high_int(int m,int n,int k)
{
int i, index=0;
for(i=99;i>=0;i--)
{
c[m][i]=(c[n][i]+c[k][i]+c[k][i]+index)%10;
index=(c[n][i]+c[k][i]+c[k][i]+index)/10;
}
return;
}
void get_list()
{
c[0][99]=1;
c[1][99]=1;
for(int i=2;i<=250;i++)
{
high_int(i,i-1,i-2);
}
return ;
}
int main()
{
get_list();
int n;
while(cin >>n)
{
int i;
for( i=0;i<100;i++)
{
if(c[n][i]!=0)
break;
}
for(i;i<100;i++)
cout<<c[n][i];
cout<<endl;
}
return 0;
}