此代碼用于以后方便復(fù)習(xí)使用，僅供參考。
數(shù)的計算 時間限制: 1 s 空間限制: 128000 KB 題目等級 : 白銀 Silver
題解 查看運行結(jié)果 題目描述 Description 我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n):
先輸入一個自然數(shù)n(n<=1000),然后對此自然數(shù)按照如下方法進行處理:
不作任何處理;
在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過原數(shù)的一半;
加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止.
輸入描述 Input Description 一個數(shù)n
輸出描述 Output Description 滿足條件的數(shù)的個數(shù)
樣例輸入 Sample Input 6
樣例輸出 Sample Output 6
數(shù)據(jù)范圍及提示 Data Size & Hint 6個數(shù)分別是：
6
16
26
126
36
136
思路： 我的思路是，記憶化dfs。根據(jù)之前算出的結(jié)果，去掉重復(fù)計算，直接返回結(jié)果。不知道有沒有更好的方法，歡迎分享！！
#include<iostream>#include<string.h>#include<math.h>using namespace std;int dp[1001];int dfs(int n){ if(dp[n]!=-1)return dp[n];//記憶化搜索，如果有直接返回數(shù)值 if(n==1){return dp[1]=1;}//dfs邊界問題，到界直接返回 else { int sum = 1;//算上自身個數(shù)，所以從1開始累加 ，如2，加上自身2，和下面返回的結(jié)果1，一共2種可能 for(int i = 1;i<=n/2;i++){ sum+=dfs(i);//這里的dfs返回的是前面能添加數(shù)的種類數(shù) } return dp[n] = sum;//將此時n統(tǒng)計的結(jié)果進行返回，返回到對應(yīng)角標數(shù)組中保存 }}int main(){ int n; cin>>n; memset(dp,-1,sizeof(dp)); cout<<dfs(n)<<endl; return 0;}新聞熱點
疑難解答
