Sephiroth's boring days!!!

核电站问题-递推动态规划

很经典的问题，由于递推公式比较诡异，所以特地的记录下来。

  1: #include <stdio.h>
  2: #define maxn 100
  3: 
  4: unsigned long long f[maxn];
  5: int n,m;
  6: 
  7: int main()
  8: {
  9:     f[0]=1;
 10:     scanf("%d%d",&n,&m);
 11:     for (int i=1;i<=n;++i)
 12:     {
 13:         f[i]=f[i-1]*2;
 14:         if (i-m-1>=0) f[i]-=f[i-m-1];
 15:         if (i-m-1==-1) f[i]-=1;
 16:     }
 17:     printf("%I64d\n",f[n]);
 18:     return 0;
 19: }
 20: 

posted on 2010-08-28 10:29 Sephiroth Lee 阅读(461) 评论(0)  编辑 收藏 引用 所属分类: 信息奥赛