2014 新年将至，微软联合CSDN英雄会共同举办本次第三届在线编程大赛，题目详情如下：
有一个字符串"iinbinbing"，截取不同位置的字符‘b’、‘i’、‘n’、‘g’组合成单词"bing"。若从1开始计数的话，则‘b’ ‘i’ ‘n’ ‘g’这4个字母出现的位置分别为(4,5,6,10) (4,5,9,10),(4,8,9,10)和(7,8,9,10)，故总共可以组合成4个单词”bing“。
咱们的问题是：现给定任意字符串，只包含小写‘b’ ‘i’ ‘n’ ‘g’这4种字母，请问一共能组合成多少个单词bing?
字符串长度不超过10000，由于结果可能比较大，请输出对10^9 + 7取余数之后的结果。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 |
#include<stdio.h>#include<string.h>int howmany (char* s){ long
long b = 0,bi = 0,bin = 0, bing = 0; unsigned int
i=0 for
(; i < strlen(s); i++) { switch
(*(s+i)) { case
‘b‘: b++; break; case
‘i‘: bi+= b; break; case
‘n‘: bin+= bi; break; case
‘g‘: bing+= bin; break; } } return
(int)(bing%1000000007);} |
使用逆推的思想，在遍历过程中，当出现‘g‘的时候，当前已经出现的"bin"和这个‘g‘都可以组成"bing"，那么"bing"的个数也就增加"bin"的个数；同理“bin”和“bi”的个数也这么算，O(n)算出结果。
原文：http://bbs.csdn.net/topics/390682748?page=1#post-396473243
原文：http://www.cnblogs.com/pavkoo/p/3549895.html