POJ 3340 Barbara Bennett'sWild Numbers(数位DP)
http://poj.org/problem?id=3340
题意:给你两个数一个是W:如36?1?8这样带问号的,一个是X如: 236428正常的数.现在要你求出所有比X数大的且与数W非问号位对应相同的所有数的个数.
分析:仔细分析一下我们可以知道.我们只需要从最高位开始比较两个数即可.
如果W的当前最高位>X的最高位,那么后面的都不用比了,可以直接用当前ans+= power(10,剩余?的个数) .因为接下来之后所有的问号都可以从0取到9个数.
如果W当前最高位<X,那么直接break即可.
否则W当前最高位==X的当前最高位,所以我们需要比较W和X的下一位.
如果W当前最高位==?,那么?只可以取[X当前最高位值,9]之间的所有值.如果?取X当前最高位值,那么后面还要继续判断.否则?取 x当前最高位值+1 , 那么ans+= power(10,剩余?的个数) .
AC代码:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
long long power(long long a,long long b)
{
long long ans=1;
for(int i=1;i<=b;i++) ans *=a;
return ans;
}
int main()
{
char a[20],b[20];
while(scanf("%s",a)==1&&strcmp(a,"#")!=0)
{
scanf("%s",b);
int cur=0,sum=0;//cur表示当前已经有多少个?,sum表示?的总数
long long ans=0;
for(int i=0;a[i];i++)if(a[i]=='?')
sum++;
for(int i=0;a[i];i++)
{
if(a[i]!='?')//a[i]与b[i]能分出胜负直接break,不能就继续比较下一位
{
if(a[i]>b[i])
{
ans += power(10,sum-cur);
break;
}
else if(a[i]<b[i]) break;
}
else if(a[i]=='?')//只要走到这步,说明前面还没有完全分出结果
{
cur++;
ans +=power(10,sum-cur)*(9-b[i]+'0');//ans加上
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
北大POJ3252-Round Numbers 解题报告+AC代码
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
电话号码的标准格式是七位十进制数,并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射,映射关系如下: A, B, 和C 映射到 2 D, E, 和F 映射到 3 G, H, 和I 映射到 4 J, K, 和L 映射到...
poj 2196 Specialized Four-Digit Numbers.md
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
北大POJ2739-Sum of Consecutive Prime Numbers 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
北大POJ1016-Numbers That Count【字符串处理】 解题报告+AC代码
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
2遍dp poj_3613解题报告 poj_3613解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告