大致题意:
给出一串数,求出这串数可能组成多少种字母排列。
大致思路:
简单DP,一定要注意0的情况
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=50000;
char str[nMax];
long long dp[nMax];
int judge(int i){
if(str[i]+str[i-1]*10>=1&&str[i]+str[i-1]*10<=26){
return 1;
}
return 0;
}
int main(){
int n,i,j,k,len;
while(scanf("%s",str)&&str[0]!='0'){
len=strlen(str);
if(len==1){
printf("1\n");
continue;
}
memset(dp,0,sizeof(dp));
for(i=0;i<len;i++)str[i]-='0';
dp[0]=1;
if(str[1]!=0){
if(judge(1))dp[1]=2;
else dp[1]=1;
}
else{
dp[1]=1;
}
for(i=2;i<len;i++){
if(str[i]==0){
if(judge(i))dp[i]=dp[i-2];
}
else{
if(judge(i)&&str[i]+str[i-1]*10>=11){
dp[i]=dp[i-1]+dp[i-2];
}
else{
dp[i]=dp[i-1];
}
}
}
printf("%lld\n",dp[len-1]);
}
return 0;
}
分享到:
相关推荐
- POJ 1860、POJ 3259:利用Dijkstra算法解决最短路径问题。 - POJ 1062、POJ 2253:涉及Bellman-Ford算法的应用场景。 - POJ 1125、POJ 2240:Floyd算法的典型实例。 ##### 最小生成树 - **算法**: - Prim...
- POJ 1753: 排序相关问题 - POJ 2965: 排序应用实例 - **搜索**:包括深度优先搜索(DFS)、广度优先搜索(BFS)等。 - **示例题目**: - POJ 1328: DFS的应用 - POJ 2109: BFS的应用 - POJ 2586: 搜索技巧展示 -...
【标题】"POJ2092:计数排序,求第K大的元素"是一个编程题目,主要涉及计数排序算法以及如何在数组中找出第K大的元素。计数排序是一种非基于比较的排序算法,它适用于整数排序,尤其在数据范围不大的情况下效率极高。...
- poj3267: 涉及到DP模型问题,适合用动态规划解决。 #### 六、数学 ##### 1. 组合数学 - **定义**: 组合数学是研究有限集合的不同计数组合方式的一门学科。 - **应用场景**: 在概率统计、计算机科学等领域广泛...
- (poj1860, poj3259, poj1062, poj2253, poj1125, poj2240):介绍迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)、弗洛伊德算法(Floyd)等。 - 使用堆优化的迪杰斯特拉算法。 3. **最小生成树...
这是西北工业大学的POJ试题的答案,欢迎下载!
### poj dp总结:动态规划分类 #### 概述 动态规划(Dynamic Programming,简称DP)是一种在计算机科学和数学中广泛使用的算法策略,用于解决最优化问题。它通过将复杂问题分解为较简单的子问题来求解,并利用这些...
POJ 2703:选择出行方式 **题目概述**: 本题目旨在通过编程的方式解决一个实际问题——选择最佳出行方式(步行或骑自行车)。题目给出了一种算法来决定在不同条件下应该采取哪种出行方式。 **代码解析**: - **...
网上整理的一些poj刷题指南。 poj地址:http://poj.org
* 类型 DP:例如 poj3267、poj1836、poj1260、poj2533。 中级 1. 基本算法: * C++的标准模版库的应用:例如 poj3096、poj3007。 * 较为复杂的模拟题的训练:例如 poj3393、poj1472、poj3371、poj1027、poj2706...
根据标题“poj 1191 经典dp 源代码”和描述中的信息,可以推测此题目是一个经典的动态规划问题。题目要求通过划分一个二维矩阵为多个不重叠的矩形区域,使得每个矩形区域的平均值与整体平均值之差的平方和最小。这个...
【标题】"poj.org算法题解集合"是关于在poj.org平台上解决的各种算法问题的集合,这个资源主要是为了帮助编程爱好者和学习者提升算法技能。poj.org是一个著名的在线编程竞赛平台,它提供了丰富的算法题目供用户实践...
### ACM新手刷题攻略之POJ ... - 推荐题目:[poj1860](https://vjudge.net/problem/POJ-1860)、[poj3259](https://vjudge.net/problem/POJ-3259)、[poj1062](https://vjudge.net/problem/POJ-1062)、[poj2253]...
1. POJ1274: 农夫John的高科技谷仓问题实质上是一个二分图的最大匹配问题。奶牛和畜栏分别代表二分图的两边,如果一头奶牛可以去某个畜栏产奶,那么就在它们之间建立边。目标是找到最大的匹配数,即最多可以同时有...
这些题目是针对ACM竞赛(ACM International Collegiate Programming Contest,简称ICPC)中的编程训练,POJ(Problem Set for Online Judges)是一个在线的编程竞赛平台,提供了许多算法和逻辑思维的练习题目。...
* 型如下表的简单 DP:型如下表的简单 DP 是指解决问题的简单 DP 算法,如 poj3267、poj1836、poj1260、poj2533。 * 计算几何学:计算几何学是指解决问题的计算几何学算法,如 poj2031、poj1039。 六、数学 数学...
《POJ 5346:四则运算表达式求值——栈与队列的应用》 在编程竞赛中,POJ 5346是一道经典的算法题目,它要求我们设计一个程序,能够处理四则运算表达式并计算其值。这个任务涉及到计算机科学中的数据结构——栈和...
【标题】"POJ1015-Jury Compromise" 是一个编程竞赛题目,主要涉及的是动态规划(Dynamic Programming, 简称DP)的算法应用。动态规划是一种解决复杂问题的有效方法,它通过将问题分解成子问题,并存储子问题的解来...
### Poj 3342 (树状DP) #### 题目背景 这是一道典型的树状动态规划问题,来源于POJ平台编号为3342的题目。题目描述了一个公司的组织结构,并提出了一种特定场景下的最优解求法。 #### 题目解析 在题目描述中提到...
- 简单DP:如`poj3267, poj1836`。 - **数学** - 组合数学:如`POJ3252, poj1850`。 - 数论:如`poj2635, poj3292`。 #### 第二阶段中级训练计划 #### 第3周至第4周(共85题) - **进阶算法** - C++标准模版...