统计特定字串模式的个数 Time Limit:1000MS Memory Limit:65536KB Total Submit:321 Accepted:173
Description
在0和1组成的长度为n（1≤n≤31）的字符串中，统计包含m（1≤m≤n）个连续1子串的字符串的个数。
Input
本题有多组测试数据。每组测试数据占一行，含n和m，表示字符串的长度和连续1的个数。n=-1和m=-1表示输入结束。
Output
对每组测试数据，在一行中输出统计出的字符串的个数。
Sample Input
1 1
2 1
3 1
4 3
10 3
10 5
20 10
20 15
31 20
31 1
-1 -1
Sample Output
1
3 7 3 520 112 6144 112 13312 2147483647
Notes
长度为4，包含3个连续1子串的字符串有3个：
0111，1110，1111
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>using namespace std;int dp[35];int main(){ int n,m; while (~scanf("%d %d", &n, &m)) { if (n == -1 && m == -1) break; dp[0] = 1; for (int i = 1; i <= n; i++) { if (i < m) dp[i] = 2 * dp[i-1]; else if (i == m) dp[i] = 2 * dp[i-1] - 1; else dp[i] = 2 * dp[i-1] - dp[i-m-1]; } PRintf("%d/n",(int)pow(2,n)-dp[n]); } return 0;}新闻热点
疑难解答
