P1028 [NOIP2001 普及组] 数的计算

解题思路：

一开始用了暴力递归，爆了 找规律+简单dp思想（递推）

• 先暴力求出前十的答案，可以发现f[i]==f[i+1]
• 当i为偶数怎么求呢？以8为例：
• 8
• 18
• 28 128
• 38 138
• 48 148 248 1248
• 可以发现前四行把8->7，就是7的情况。最后一行把把删掉就是4的情况

解题代码1（暴力）：

#include<bits/stdc++.h>
using namespace std;
void deal(int n,int &cnt){
	if(n&1) n--;
	n/=2;
	cnt+=n;
	for(int i=n;i>0;i--) deal(i,cnt);
}
int main(){
	int n;
	while(cin>>n){
		int cnt=0;
		deal(n,cnt);
		cout<<cnt+1<<endl;
	}
	return 0;
} 

解题代码2：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int f[1001]={0};
	f[0]=1;f[2]=2;f[1]=1;
	for(int i=3;i<=n;i++){
		if(i&1) f[i]=f[i-1];
		else f[i]=f[i-1]+f[i/2]; 
	}
	cout<<f[n]<<endl;
	return 0;
}