数的计算
题目的链接：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1010题目的描述：
数的计算
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:531 测试通过:162
描述
要求找出具有下列性质数的个数（包含输入的自然数n）：
先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:
1. 不作任何处理;
2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
3. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
输入
一个自然数n
输出
一个数，表示满足条件的数的个数
样例输入
6
样例输出
6
提示
样例说明：满足条件的数是6，16，26，126，36，136
开始用搜索做，递归一开，那华丽丽的TLE啊....最后改用DP。
其实DP 的关键在于找到子问题的结构。
我们规定arr为在j左边填写i时的数的个数，很明显：
arr=a+a+...+arr(i<=j/2)
我们首先规定
arr=1(0<=t<=n,n为输入的自然数)，因为左边填0时就为本数，数的个数当然为1.
按照子问题结构，先解子问题，再得到原问题的解。
代码如下：
#include<iostream>using namespace std;int arr;int main(){ int n; cin>>n; for(int i=0;i<=500;i++) { for(int j=0;j<=1000;j++) { arr=0; } } for(int i=1;i<=1000;i++) { arr=1; } for(int i=0;i<=n;i++) { for(int j=1;j<=i/2;j++) { for(int k=0;k<j;k++) { arr+=arr; } } } int sum=0; for(int i=0;i<=n/2;i++) { sum+=arr; } cout<<sum<<endl; system("pause"); return 0;}
页:
[1]