Initiate

Call A Spade a Spade
posts - 14, comments - 3, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

POJ2506 递推+高精

Posted on 2010-02-15 22:04 Initiate 阅读(265) 评论(0)  编辑 收藏 引用

给看似复杂的题找到了合适的规律就会变得简单。

这个题就是这样。对于n列来说,可以在n-1列的基础上加上一块,或者是在n-2列的基础上加上2块

而2块独立的,不依赖于1块的情况有两种,所以得到递推公式f(n)=f(n-1)+2f(n-2)

看样例,要用到高精。

#include<iostream>
//f(n)=f(n-1)+2f(n-2)
using namespace std;
int f[251][300];
void HPprint(int *a)
{
    for (int i=a[0];i>=1;i--) cout<<a[i];
    cout<<endl;
}

void HPplus(int *a,int *b,int *c)
{
int i,j;
j=0;
for(i=1;i<=min(a[0],b[0]);i++)
{
   c[i]=a[i]+b[i]+j;
   j=c[i]/10;
   c[i]%=10;
   }
if(j!=0) c[i]=j;
c[0]=a[0]>b[0]?a[0]+2:b[0]+2;
while(c[c[0]]==0 && c[0]>1) c[0]--;
}
void HPmultyNUM(int *a,int b,int *c)
{
    int i,j,k;
    for (i=1;i<=a[0];i++)
        c[i]+=a[i]*b;
        k=0;
    for (j=1;j<=a[0];j++)
        {
            c[j]+=k;
            k=c[j]/10;
            c[j]%=10;
        }//进位
    if(k!=0) c[j]=k;
    c[0]=a[0]+3;
    while (c[c[0]]==0 && c[0]>1) c[0]--;   
}
int main()
{
int i,j,t[300],test;
f[0][0]=1;f[0][1]=1;
f[1][0]=1;f[1][1]=1;f[2][0]=1;f[2][1]=3;
for(i=3;i<=250;i++)
{
   memset(t,0,sizeof(t));
   HPmultyNUM(f[i-2],2,t);
   HPplus(t,f[i-1],f[i]);
}
while(cin>>test)
   HPprint(f[test]);
return 0;
}

阅读全文
类别:Poj 查看评论

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理