题目大意:给出n根火柴,问说能组成多少种数字,要求说0不能打头。
解题思路:d[i]表示i根火柴能够组成的数量,d[i+c[j]] = d[i+c[j]] + d[i];
最后dp[i]表示小于等于i根火柴能组成的数量,dp[i]=∑jidp[j].
高精度。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 505;
struct bign {
int len, num[MAXN];
bign () {
len = 0;
memset(num, 0, sizeof(num));
}
bign (int number) {*this = number;}
bign (const char* number) {*this = number;}
void DelZero ();
void Put ();
void operator = (int number);
void operator = (char* number);
bool operator < (const bign& b) const;
bool operator > (const bign& b) const { return b < *this; }
bool operator <= (const bign& b) const { return !(b < *this); }
bool operator >= (const bign& b) const { return !(*this < b); }
bool operator != (const bign& b) const { return b < *this || *this < b;}
bool operator == (const bign& b) const { return !(b != *this); }
void operator ++ ();
void operator -- ();
bign operator + (const int& b);
bign operator + (const bign& b);
bign operator - (const int& b);
bign operator - (const bign& b);
bign operator * (const int& b);
bign operator * (const bign& b);
bign operator / (const int& b);
int operator % (const int& b);
};
const int N = 2005;
const int c[20] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
bign dp[N];
int main () {
dp[0] = 1;
dp[1] = 0;
for (int i = 0; i <= 2000; i++) {
for (int j = 0; j < 10; j++) {
if (i == 0 && j == 0)
continue;
if (i + c[j] <= 2000)
dp[i+c[j]] = dp[i+c[j]] + dp[i];
}
}
dp[6] = dp[6] + 1;
for (int i = 2; i <= 2000; i++)
dp[i] = dp[i] + dp[i-1];
int n;
while (scanf("%d", &n) == 1 && n > 0) {
dp[n].Put();
printf("\n");
}
return 0;
}
void bign::DelZero () {
while (len && num[len-1] == 0)
len--;
if (len == 0) {
num[len++] = 0;
}
}
void bign::Put () {
for (int i = len-1; i >= 0; i--)
printf("%d", num[i]);
}
void bign::operator = (char* number) {
len = strlen (number);
for (int i = 0; i < len; i++)
num[i] = number[len-i-1] - '0';
DelZero ();
}
void bign::operator = (int number) {
len = 0;
while (number) {
num[len++] = number%10;
number /= 10;
}
DelZero ();
}
bool bign::operator < (const bign& b) const {
if (len != b.len)
return len < b.len;
for (int i = len-1; i >= 0; i--)
if (num[i] != b.num[i])
return num[i] < b.num[i];
return false;
}
void bign::operator ++ () {
int s = 1;
for (int i = 0; i < len; i++) {
s = s + num[i];
num[i] = s % 10;
s /= 10;
if (!s) break;
}
while (s) {
num[len++] = s%10;
s /= 10;
}
}
void bign::operator -- () {
if (num[0] == 0 && len == 1) return;
int s = -1;
for (int i = 0; i < len; i++) {
s = s + num[i];
num[i] = (s + 10) % 10;
if (s >= 0) break;
}
DelZero ();
}
bign bign::operator + (const int& b) {
bign a = b;
return *this + a;
}
bign bign::operator + (const bign& b) {
int bignSum = 0;
bign ans;
for (int i = 0; i < len || i < b.len; i++) {
if (i < len) bignSum += num[i];
if (i < b.len) bignSum += b.num[i];
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
}
while (bignSum) {
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
}
return ans;
}
bign bign::operator - (const int& b) {
bign a = b;
return *this - a;
}
bign bign::operator - (const bign& b) {
int bignSub = 0;
bign ans;
for (int i = 0; i < len || i < b.len; i++) {
bignSub += num[i];
bignSub -= b.num[i];
ans.num[ans.len++] = (bignSub + 10) % 10;
if (bignSub < 0) bignSub = -1;
}
ans.DelZero ();
return ans;
}
bign bign::operator * (const int& b) {
int bignSum = 0;
bign ans;
ans.len = len;
for (int i = 0; i < len; i++) {
bignSum += num[i] * b;
ans.num[i] = bignSum % 10;
bignSum /= 10;
}
while (bignSum) {
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
}
return ans;
}
bign bign::operator * (const bign& b) {
bign ans;
ans.len = 0;
for (int i = 0; i < len; i++){
int bignSum = 0;
for (int j = 0; j < b.len; j++){
bignSum += num[i] * b.num[j] + ans.num[i+j];
ans.num[i+j] = bignSum % 10;
bignSum /= 10;
}
ans.len = i + b.len;
while (bignSum){
ans.num[ans.len++] = bignSum % 10;
bignSum /= 10;
}
}
return ans;
}
bign bign::operator / (const int& b) {
bign ans;
int s = 0;
for (int i = len-1; i >= 0; i--) {
s = s * 10 + num[i];
ans.num[i] = s/b;
s %= b;
}
ans.len = len;
ans.DelZero ();
return ans;
}
int bign::operator % (const int& b) {
bign ans;
int s = 0;
for (int i = len-1; i >= 0; i--) {
s = s * 10 + num[i];
ans.num[i] = s/b;
s %= b;
}
return s;
}
分享到:
相关推荐
自适应控制--递推最小二乘参数估计 自适应控制--递推最小二乘参数估计
算法专项练习---递推.ppt
递推公式的伟大意义——?常见的编程实现方法?(优缺点?)有了公式,人工计算的方法?
线性代数- 线性递推关系.rar
行业分类-外包设计-基于递推增广最小二乘法的结晶器ARMAX模型辨识方法的说明分析.rar
行业分类-外包设计-基于递推最小二乘法RLS的结晶器ARX模型辨识方法的说明分析.rar
行业分类-外包设计-基于递推工具变量法RIV的结晶器ARX模型辨识方法的说明分析.rar
行业分类-外包设计-基于递推岭ELM的填料塔载点气速预测方法的说明分析.rar
行业分类-外包设计-基于递推最小二乘法的空调所属建筑物一阶模型实时参数辨识方法的说明分析.rar
算法-求递推序列的第N项(51Nod-1126)(包含源程序).rar
2014届高中三年级数学一轮复习-专家讲坛-由递推公式求通项的7种方法及破解数列中的4类探索性问题-理.doc
1.该资源包括自己编写的burg、levinson-durbin递推法的AR参数模型功率谱估计 2.代码有很详细的注释 3.对大家理解AR参数模型估计功率谱有很大的帮助
专门训练算法的讲稿,很不错哦!
自适应控制---遗忘因子递推最小二乘参数估计 自适应控制---遗忘因子递推最小二乘参数估计
主要讲组合数中母函数与递推关系,方便大家学习
NOIP基础算法--枚举、递推和递归 很有用的哦,看看有好处的
综合车辆运行过程中不同时段的路况差异和人因作用、突发道路事故随机性, 以神经网络有师学习作为经验累积方法, 提出时间递推预测方法确定路径最短时间, 从而实现对交通路径的动态诱导。递推预测以知识库累积经验与...
基于递推最小二乘算法的太阳能新风系统参数辨识,包红霞,杨军,太阳能新风系统,是利用太阳能加热新风送到室内来实现房间的通风与换气,并对室内供暖起到辅助作用的空调系统。应用最经典的递推
由于目前分数阶混沌的理论分析和硬件设计都比较烦琐,提出了分数阶混沌系统的Simulink动态仿真方法。以分数阶Jerk系统为例,根据分数阶系统方程搭建分数阶混沌系统仿真模型,可动态地观察系统变量的变化规律。...
利用周期图法进行谱估计,并绘制结果,窗函数采用...利用Levinson-Durbin递推法求解Yule-walker方程,进行AR(6)的建模。与Matlab中periodogram(周期图)和pyulear(Yule-walker方程)中相应方法的结果进行比较和分析。