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

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

// dp[i][j][k] 意思是长为 i 的序列中 0 比 1 最多多 j 个，且长为 i 的序列中 1 比 0 最多多 k 个这样的序列的个数

所以 j，k最小为 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

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 int n,m;

 LL dp[][][]; //长为 i 的序列，0比1最多多 j 个，且1比0最多多 k 个

 int main()

 {

     while (scanf("%d%d",&n,&m)!=EOF)

     {

         memset(dp,,sizeof(dp));

         dp[][][]=;

         for (int i=;i<=n;i++)

         {

             for (int j=;j<=m;j++)

             {

                 for (int k=;k<=m;k++)

                 {

                     dp[i+][j+][max(k-,)]+=dp[i][j][k];  // 下一个数是 0

                     dp[i+][max(j-,)][k+]+=dp[i][j][k];  // 下一个数是 1

                 }

             }

         }

         LL ans = ;

         for (int i=;i<=m;i++)

             for (int j=;j<=m;j++)

                 ans += dp[n][i][j];

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

01-K Code

最新文章

热门文章