题意分析

本题要求计算长度为 ( n ) 的二进制字符串中，相邻两个1的对数恰好为 ( k ) 的字符串数目。相邻1的对数通过公式 ( \text{AdjBC}(x) = \sum_{i=1}^{n-1} x_i x_{i+1} ) 计算，其中 ( x_i ) 为0或1。

解题思路

动态规划建模

定义状态 ( dp[i][j][s] ) 表示长度为 ( i ) 的字符串，相邻1的对数为 ( j )，且最后一位为 ( s )（( s ) 取0或1）时的字符串数目。状态转移需考虑最后一位添加0或1对相邻对数的影响：

• 添加0：若前一位为0，相邻对数不变；若前一位为1，相邻对数不变（因为末尾添加0不会产生新的相邻1）。
• 添加1：若前一位为1，相邻对数增加1；若前一位为0，相邻对数不变。

状态转移方程

• 当前位为0：
  [ dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] ]
  无论前一位是0或1，添加0后末尾为0，相邻对数不变。

• 当前位为1：
  [ dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1] ]

  • 若前一位为0，添加1后末尾为1，相邻对数不变（无新增相邻1）。
  • 若前一位为1，添加1后末尾为1，相邻对数需增加1，因此前一状态的相邻对数应为 ( j-1 )。

初始条件

• 当 ( i=1 ) 时，字符串只有一位，相邻对数为0：
  [ dp[1][0][0] = 1, \quad dp[1][0][1] = 1 ]

实现步骤

1. 初始化动态规划表：使用三维数组或二维数组（优化空间）存储状态。由于 ( n \leq 100 )，直接使用二维数组 ( dp[j][s] ) 表示当前长度下的状态，滚动更新。
2. 状态转移：从长度2到 ( n )，依次计算每个长度下的相邻对数 ( j ) 的可能值。
3. 结果合并：对于长度为 ( n ) 的字符串，结果为 ( dp[n][k][0] + dp[n][k][1] )，即末尾为0或1时相邻对数为 ( k ) 的数目之和。

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#define maxn 105
using namespace std;
int main()
{
    int t,n,m;
    int dp[maxn][maxn][2];
    dp[1][0][0] = dp[1][0][1] = 1;
    for(int i=2;i<maxn;i++){
        dp[i][0][0] = dp[i-1][0][1] + dp[i-1][0][0];
        dp[i][0][1] = dp[i-1][0][0];
    }
    for(int i=2;i<maxn;i++){
        for(int j=1;j<maxn;j++){
            dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1];
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1];
        }
    }
    int T;
    cin >> T;
    while(T--){
        cin >> t >> n >> m;
        cout << t << " " << dp[n][m][0]+dp[n][m][1] << endl;
    }
    return 0; 
}