博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
sicily 1001. Alphacode (DP)
阅读量:7289 次
发布时间:2019-06-30

本文共 1138 字,大约阅读时间需要 3 分钟。

题目:http://soj.me/1001

一串数字问一共有多少种编码的可能性

思路:

code[i]为题目给出的数字(i从零开始)

当i>=2时

如果code[i]=0

  case1:ans[i]=ans[i-2](因为code[i-1]不能单独存在 必须与code[i]合并,如3120,ans[1]=1,ans[2]=2,ans[3]=1)

如果code[i]!=0

  如果code[i-1]=0

    case2:ans[i]=ans[i-1](code[i]必须单独存在,如3102,ans[1]=1,ans[2]=1,ans[3]=1)

  如果code[i-1]!=0

    如果code[i-1]与code[i]合并<=26

      case3:ans[i]=ans[i-1]+ans[i-2](code[i]和code[i+1]可合并也可单独分开,若合并则ans[i]=ans[i-2] 参见case1,若分开则ans[i]=ans[i-1]参见case2,如3124,ans[1]=1,ans[2]=2,ans[3]=3)

    如果code[i-1]与code[i]合并>26

      case4:ans[i]=ans[i-1](code[i]和code[i+1]必须分开参见case2 如code[i]=1234 ans[1]=2,ans[2]=3,ans[3]=3)

#include 
#include
using namespace std; int main(){ string code; long long ans[100000]; int n; while (cin>>code&&code!="0") { int len=code.size(); if (len == 1) { cout << "1" << endl; continue; } n = (code[0]-'0')*10+code[1]-'0'; ans[0]=1; if (n<=26&&code[1]!='0') ans[1] = 2; else ans[1]=1; for (int i=2;i

 

 

 

 

 

 

转载于:https://www.cnblogs.com/danielqiu/archive/2013/01/23/2872987.html

你可能感兴趣的文章
将博客搬至CSDN
查看>>
如何mac下安装virtual,并识别usb接口
查看>>
Ansible批量部署zabbix-agent
查看>>
使用PowerShell对比两个服务器系统进程和软件清单
查看>>
线程池的概述和使用学习笔记
查看>>
oracle基础之日志系列
查看>>
【NetApp】移动磁盘柜到一个新的控制器
查看>>
实在太伟大了,感谢楼主共享深度爬取和广度爬取
查看>>
crontab调用python时出现ImportError: No module named XXX的问题
查看>>
方正智睿NoSQL数据库总体介绍
查看>>
CentOS6.9安装Redis4.0.0
查看>>
Android 监听事件
查看>>
基于CentOS6.5环境之下的LNMP之编译安装mysql5.6.27
查看>>
《系统运维全面解析:技术、管理与实践》纠错汇总
查看>>
Object类对线程的支持----等待与唤醒
查看>>
硬盘串口和并口的区别
查看>>
java multithreading server example
查看>>
自动分发神器搭建kickstart
查看>>
我的友情链接
查看>>
mysql主从复制,半同步,主主复制架构的实现
查看>>