题目的链接:
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;
}
分享到:
相关推荐
### 电机线圈匝数计算方法及应用 电机线圈匝数的计算是电机设计与维修中的一个重要环节,它直接影响到电机的性能和效率。本文将详细介绍如何计算电机线圈的匝数,并结合实例帮助读者更好地理解这一过程。 #### 一...
轨道根数计算是卫星导航定位领域中的一个重要概念,它与我们日常生活中使用的GPS、北斗、伽利略等全球导航卫星系统(GNSS)密切相关。轨道根数,也称为Keplerian元素,是一组参数,用于描述地球轨道上的卫星运动状态...
**MATLAB工具箱大全- 分形维数计算工具箱FracLab 2.2** MATLAB是一款强大的数学计算软件,广泛应用于科学研究、工程计算以及数据分析等领域。FracLab 2.2是MATLAB的一个专业工具箱,专为分形维数计算而设计,它为...
在MATLAB中,分形维数的计算是数学与计算机科学的一个重要领域,特别是在图像处理、几何形态学和复杂系统的研究中。分形维数是一种描述不规则形状复杂性的度量,它超越了传统的欧几里得几何维度,能够更好地刻画现实...
本主题将深入探讨如何使用MATLAB来计算分形维数,特别是针对二值图像的情况。 首先,我们需要理解什么是分形。分形是具有自相似性的几何对象,即使在不同尺度下观察,其形态仍然保持相似。它们通常具有非整数的维度...
javascript版本的轨道六根数计算卫星位置的函数 /* 参数例子: orbitPara = { o: 20,//升交点赤径(单位度) i: 30,//轨道倾角(单位度) w: 10,//近地点角距(单位度) a: 7000e+3,//半长轴(单位米) e: 0.5,//离心...
在IT领域,分形维数计算是复杂系统和非规则形状研究的重要工具,尤其是在图像处理、信号分析和自然科学中有着广泛的应用。MATLAB作为一种强大的数值计算软件,为分形理论的实现提供了便利。本篇文章将深入探讨标题和...
通过分形维数的计算,可以对土壤表面的复杂性和粗糙度进行量化表征。分形理论最早由法国数学家Mandelbrot在20世纪70年代提出,其主要研究非线性系统中的不规则、不可微、极不规则的几何形体。由于土壤表面的这些特性...
本资源中包含了多种计算题型,例如,二位数乘二位数,三位数乘二位数,二位数乘三位数等等。这些题型可以帮助学生更好地理解乘法的基本规则和计算策略。 知识点5:应用问题 在本资源中,我们可以看到一些应用问题...
本程序"扼流圈匝数计算小程序"正是为了解决这一问题而设计的,旨在帮助工程师和爱好者快速准确地计算出适合特定应用的扼流圈匝数。 扼流圈的电感L计算公式通常为: \[ L = N^2 \cdot \mu \cdot A / l \] 其中: -...
分形维数计算ArcGIS工具箱 直接导入到ArcGIS中即可使用,用于计算栅格和矢量数据的分形维数值,使用简单。 此外,工具箱中还增加了批量按掩膜提取、批量裁剪等多种功能,一次下载永久使用,工具箱中的工具均为自己...
在本软件"二维图像分形维数计算软件"中,用户可以利用MATLAB环境对各种二维图形进行深入的分形分析。MATLAB是一种广泛使用的编程和数值计算平台,非常适合进行复杂的数学运算和图像处理。 分形维数是一种特殊的维数...
千斤顶标定后与油表对应读数计算,直接输入相应参数即可,简单,方便,易懂。
- **方法一**:将FPGA的基本单元与实现相同功能的标准门阵列进行比较,标准门阵列中包含的门数即为该FPGA基本单元的等效门数,然后乘以基本单元的数目即可得到FPGA的等效门数估计值。 - **方法二**:分别用FPGA和...
matlab版本根据卫星的轨道六根数计算卫星轨道的函数 输入[升交点赤径 轨道倾角 近地点角距 半长轴 离心率 真近点角]和时间 输出对应时间的位置和速度
js双色球方案注数、方案所有中奖情况、奖金计算的核心代码,可做参考。 每个方法均有注释
标题“分形.zip_关联维数计算_分形关联维数_分形维数计算_分形计算_数据分形维数”涉及到的关键知识点包括关联维数计算、分形关联维数、分形维数计算、分形计算以及数据分形维数。下面将对这些概念进行详细的解释和...
二维图像的计盒维数(Box-Counting Dimension)是一种常用的计算分形维数的方法,它可以帮助我们理解和描述复杂形状的结构特征。在本主题中,我们将深入探讨计盒维数的概念、Python实现以及如何利用它来分析图像的...
接近数计算是数学和计算机科学中的一个重要概念,通常涉及到数值分析和算法设计。在易语言中实现接近数计算,可以帮助我们解决一些需要进行数值估算或优化的问题。 在易语言中进行接近数计算,主要涉及以下几个知识...
利用 MATLAB 计算分形维数 在图像处理领域中,分形维数是衡量图像复杂度的重要指标。本文将介绍如何使用 MATLAB 计算二维图像的分形维数,并对分形维数的计算过程进行详细解释。 分形维数的定义 分形维数...