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&gt;=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 >&gt;n)
 {
  int i;
  for( i=0;i&lt;100;i++)
  {
   if(c[n][i]!=0)
    break;
  }
  for(i;i&lt;100;i++)
   cout&lt;&lt;c[n][i];
  cout&lt;&lt;endl;
 }
 return 0;
}