我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
简单的递推dp[n]=dp[n/2]+…+dp[1]+n/2(因为每加一个就多一个，一共加了n/2个);
所以代码如下
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x)) #define ss(x) scanf("%s",(x)) #define maxn 50005 const int inf=0x3f3f3f3f; const ll mod=1000000007; int dp[1005]; int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif for(int i=1;i<=1000;i++) { for(int j=1;j<=i/2;j++) { dp[i]+=dp[j]+1; } } int n; cin>>n; cout<<dp[n]+1<<endl; #ifdef local printf("time: %d\n",int(clock()-_time)); #endif }
原文：http://www.cnblogs.com/scau-zk/p/5633846.html
