poj 3340給定兩個(gè)字符串：s跟t，長(zhǎng)度一樣，均不超過(guò)10，但t只包含數(shù)字，而s除了數(shù)字還可能含有"?"，問(wèn)將問(wèn)號(hào)變成數(shù)字后得到的數(shù)字中，有多少個(gè)數(shù)是大于t的。
很明顯用搜索找出所有符合要求的數(shù)字即可。
搜索從s的第一個(gè)字符s[0]開(kāi)始，每次向下遞歸都檢查s的下一個(gè)字符s[level]。根據(jù)當(dāng)前字符有一下幾種搜索方向：
1. s[level]=='?'， 設(shè)當(dāng)前值為now，則下一個(gè)值可以是now*10+i, 0<=i<=9，只要這個(gè)值大于等于t[0~level]所表示的數(shù)字，則進(jìn)入下一層遞歸：
dfs(now*10+i, level+1)。
2. s[level]是一個(gè)數(shù)字要分兩種情況討論：若now*10+s[level]-'0'>=t[0~level]表示的數(shù)字，則dfs(now*10+s[level]-'0', level+1)；否則就返回0，表示s跟t從0
到level這一段不符合要求。
搜索的時(shí)候要注意優(yōu)化，否則當(dāng)s=“????????", t="00000000"時(shí)就要算很久。優(yōu)化是當(dāng)now*10+i > t[0~level]時(shí)，則j>i的情況都不用再遞歸計(jì)算了，因?yàn)閐fs( now*10+{i+1 ,..., 9}, level+1)的結(jié)果跟dfs(now*10+i, level+1)的結(jié)果是一樣的。只要乘上9-i就可以了。
1 #include <iostream>
2
3 using namespace std;
4
5 char s[11],t[11];
6 int tt[11];
7 int fact[11];
8 int cnt;
9 int len;
10
11 __int64 dfs(int now,int level)
12 {
13 if(level==len){
14 if(now>tt[level-1]) return 1;//cnt+=(now%fact[level-1]-tt[level-1]%fact[level-1]);
15 return 0;
16 }
17 // 用0~9十個(gè)數(shù)字來(lái)代替?
18 if(s[level]=='?'){
19 int i=0;
20 while(i<10 && now*10+i<tt[level]) i++;
21 __int64 tmp=dfs(now*10+i,level+1);
22 if(i+1<10) tmp+=(9-i)*dfs(now*10+i+1,level+1);
23 return tmp;
24 }else if(now*10+s[level]-'0'>=tt[level]){
25 return dfs(now*10+s[level]-'0',level+1);
26 }else{
27 return 0;
28 }
29 }
30
31 void solve()
32 {
33 int i,j,k;
34 len=strlen(s);
35 tt[0]=t[0]-'0';
36 for(i=1;i<len;i++) tt[i]=tt[i-1]*10+t[i]-'0';
37 cnt=0;
38 printf("%I64d\n",dfs(0,0));
39 }
40
41 int main()
42 {
43 fact[0]=1;
44 for(int i=1;i<=10;i++) fact[i]=fact[i-1]*10;
45 while(true){
46 scanf("%s",s);
47 if(s[0]=='#') return 1;
48 scanf("%s",t);
49 solve();
50 }
51 }
52