★?? 輸入文件：nucle.in?? 輸出文件：nucle.out???簡單對比
時間限制：1 s?? 內存限制：128 MB
【問題描述】
????一個核電站有 N 個放核物質的坑，坑排列在一條直線上。如果連續 M 個坑中放入核物質，則會發生爆炸，于是，在某些坑中可能不放核物質。
任務：對于給定的 N 和 M ，求不發生爆炸的放置核物質的方案總數。
【輸入格式】?
???? 輸入文件（nucle.in）只一行，兩個正整數 N ， M( 1<N<50 ， 2 ≤ M ≤ 5)
【輸出格式】?
???? 輸出文件 (nucle.out) 只有一個正整數 S ，表示方案總數。
【輸入輸出樣例】
?
輸入：
nucle.in
4 3
輸出：
nucle.out
13
?
思路：
若用f[i]儲存在這個坑時的已經計算過的所有情況
對于一個坑，有三種情況
1：n<m在這種情況下只有兩種情況
?? 放與不放。于是此時所有的情況就是2*f[i-1]
2：n==m
?? 這種情況下也可以選擇放與不放，但是當放的時候，若前n-1個已經放了物質，則第n個不能放
? 于是所有的情況就是2*f[i-1]-1
3:n>m
? 當選擇不放的時候，就是加上f[i-1]的所有情況
?? 當選擇放的時候，要考慮若放上會爆炸的情況，我們先想若放上之后不爆炸的情況，就是f[i-1]，再減去放上之后會爆炸的情況。那么放上之后會爆炸的情況是什么呢？如果我們放上會爆炸，那么i-m-1個一定沒有放。所以放上會爆炸的情況就是f[i-m-1].
So這種情況下的所有情況就是2*f[i-1]-f[i-m-1]
?
1 #include<cstdio> 2 using namespace std; 3 int main() 4 { 5 freopen("nucle.in","r",stdin); 6 freopen("nucle.out","w",stdout); 7 long long f[50]; 8 int i,n,m; 9 cin>>n>>m; 10 f[0]=1; 11 for(i=1;i<=n;i++) 12 { 13 if(i<m) f[i]=2*f[i-1]; 14 if(i==m) f[i]=2*f[i-1]-1; 15 if(i>m) f[i]=2*f[i-1]-f[i-m-1]; 16 } 17 cout<<f[n]<<endl; 18 return 0; 19 }
?
 網絡編程學習--簡易網站服務器)
