ZZUOJ1196: 单调数-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

ZZUOJ1196: 单调数

阅读量：5984 次

发布时间：2019-06-20

本文共 860 字，大约阅读时间需要 2 分钟。

/*

注意的事项:是输出小于 10^n的正整数的个数哦！开始的时候总比样例输出多一个数，

纠结了好久，原来是 0加了进去了！

dpI[n][m]表示的是第n位添加数字m（0....9）的构成单调递增数个数

dpD[n][m]表示的是第n位添加数字m（0....9）的构成单调递减数个数

*/

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

long long dpI[105][10];

long long dpD[105][10];

void init(){

for(int i=1; i<10; ++i)

dpI[1][i]=dpD[1][i]=1;

for(int i=2; i<=100; ++i){

for(int j=0; j<10; ++j){

if(j!=0){//单调递增的数一定没有数字0，因为前边的数字最小为 1

for(int k=j; k>=1; --k)

dpI[i][j]+=dpI[i-1][k];

}

for(int k=j; k<10; ++k){//单调递减的数字中可以有0，但是第二位为0时，第一位不能为0

if(i==2 && k==0) continue;

dpD[i][j]+=dpD[i-1][k];

}

}

}

}

int main(){

init();

int n;

while(cin>>n){

long long sum=0;

for(int j=1; j<=n; ++j){

for(int i=0; i<10; ++i)

sum+=dpI[j][i]+dpD[j][i];

sum-=9;

}

cout<<sum<<endl;

}

return 0;

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3913685.html，如需转载请自行联系原作者

你可能感兴趣的文章

CentOS 6.x 快速安装L2TP ***

一篇文章能够看懂基础源代码之JAVA篇

Goldengate双向复制配置

Oracle官方内部MAA教程

DNS相关配置

miniWindbg 功能

《Cisco IPv6网络实现技术（修订版）》一2.6　配置练习：使用Cisco路由器配置一个IPv6网络...

《可穿戴创意设计：技术与时尚的融合》一一第2章与可穿戴设备有关的故事...

ruby动态new对象

Linux中grep命令的12个实践例子

使用Docker Compose部署基于Sentinel的高可用Redis集群

Mybatis 3学习笔记（一）

Guice系列之用户指南（十）

树与森林的存储、遍历和树与森林的转换

Android自定义属性

Visual C#之核心语言

代码重构(五)：继承关系重构规则

Windows App开发之集合控件与数据绑定

中大型网站技术架构演变过程

ARTS训练第三周

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-12-29 22:45:03 当前IP: 18.116.13.192 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我