核電站問題-遞推動態規劃

很經典的問題，由于遞推公式比較詭異，所以特地的記錄下來。

  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 閱讀(491) 評論(0)  編輯 收藏 引用 所屬分類: 信息奧賽