首页 > 代码库 > 01-K Code

01-K Code

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 728    Accepted Submission(s): 209


Problem Description

Consider a code string S of N symbols, each symbol can only be 0 or 1. In any consecutive substring of S, the number of 0‘s differs from the number of 1‘s by at most K. How many such valid code strings S are there? 

For example, when N is 4, and K is 3, there are two invalid codes: 0000 and 1111. 

 

 

Input

The input consists of several test cases. For each case, there are two positive integers N and K in a line.

N is in the range of [1, 62].

K is in the range of [2, 5].

 

 

Output

Output the number of valid code strings in a line for each case.

 

 

Sample Input

 

1 2
4 3

 

 

 

Sample Output

2

14

 

 

//有一个长为 i 的 0-1 组成的序列,问任意连续长的子序列 0 1 数量差都不超过 m 的情况多少种

// dp[i][j][k] 意思是长为 i 的序列的子序列中 0 比 1 最多多 j 个,且长为 i 的序列的子序列中 1 比 0 最多多 k 个

所以 i,j 最小为 0

dp [i][j][k] = dp[i-1][max(0,j-1)][k+1] // 填 1

                +dp[i-1][j+1][max(0,k-1)]  // 填 0

技术分享
 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4   5 int n,m; 6 LL dp[105][10][10]; //长为 i 的序列,0比1最多多 j 个,且1比0最多多 k 个 7   8 int main() 9 {10     while (scanf("%d%d",&n,&m)!=EOF)11     {12         memset(dp,0,sizeof(dp));13         dp[0][0][0]=1;14         for (int i=0;i<=n;i++)15         {16             for (int j=0;j<=m;j++)17             {18                 for (int k=0;k<=m;k++)19                 {20                     dp[i+1][j+1][max(k-1,0)]+=dp[i][j][k];  // 下一个数是 021                     dp[i+1][max(j-1,0)][k+1]+=dp[i][j][k];  // 下一个数是 122                 }23             }24         }25         LL ans = 0;26         for (int i=0;i<=m;i++)27             for (int j=0;j<=m;j++)28                 ans += dp[n][i][j];29         printf("%lld\n",ans);30     }31     return 0;32 }
View Code

 

 

01-K Code