数的计算_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > 数的计算

数的计算

 2012/5/10 10:39:45  passzh  程序员俱乐部  我要评论(0)
  • 摘要:题目的链接:http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1010题目的描述:数的计算时间限制(普通/Java):1000MS/3000MS运行内存限制:65536KByte总提交:531测试通过:162描述要求找出具有下列性质数的个数(包含输入的自然数n):先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:1.不作任何处理;2.在它的左边加上一个自然数
  • 标签:
题目的链接: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[i][j]为在j左边填写i时的数的个数,很明显:
arr[i][j]=a[0][i]+a[1][i]+...+arr[i/2][i](i<=j/2)
我们首先规定
arr[0][t]=1(0<=t<=n,n为输入的自然数),因为左边填0时就为本数,数的个数当然为1.
按照子问题结构,先解子问题,再得到原问题的解。
代码如下:
#include<iostream>
using namespace std;
int arr[501][1001];
int main()
{
   int n;
   cin>>n;
   for(int i=0;i<=500;i++)
   {
       for(int j=0;j<=1000;j++)
       {
           arr[i][j]=0; 
       } 
   }
   for(int i=1;i<=1000;i++)
   {
       arr[0][i]=1;
   }
   for(int i=0;i<=n;i++)
   {
      for(int j=1;j<=i/2;j++)
      {
          for(int k=0;k<j;k++)
          {
              arr[j][i]+=arr[k][j]; 
          }
      }
   }
   int sum=0;
   for(int i=0;i<=n/2;i++)
   {
      sum+=arr[i][n]; 
   }
   cout<<sum<<endl;
   
   system("pause");
   return 0;
}
  • 相关文章
发表评论
用户名: 匿名