11100, 01110, 00111, 10111, 11101, 11011
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a decimal integer giving the number (n) of bits in the bit strings, followed by a single space, followed by a decimal integer (k) giving the desired adjacent bit count. The number of bits (n) will not be greater than 100 and the parameters n and k will be chosen so that the result will fit in a signed 32-bit integer.
For each data set there is one line of output. It contains the data set number followed by a single space, followed by the number of n-bit strings with adjacent bit count equal to k.
10 1 5 2 2 20 8 3 30 17 4 40 24 5 50 37 6 60 52 7 70 59 8 80 73 9 90 84 10 100 90
1 6 2 63426 3 1861225 4 168212501 5 44874764 6 160916 7 22937308 8 99167 9 15476 10 23076518
解题思路：用dp[i][j][k]来定义状态。i表示当前数字是第i位，j表示达到j值，k代表末尾是0还是1.由于当末尾为0对新加的一位没有要求，即j值不会变动，所以当dp[i][j][0]时转移方程为dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1]。而当末尾为1时如果新加一位的值为1，会影响j的值。所以当dp[i][j][1]时dp[i][j][1]=dp[i-1][j-1][1]+dp[i-1][j][0]。
#include<bits/stdc++.h>
using namespace std;
int dp[500][500][2];
void DP(int n){
memset(dp,0,sizeof(dp));
dp[1][0][0]=1;
dp[1][0][1]=1;
for(int i=2;i<n;i++){
for(int j=0;j<i;j++){
dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
if(j){
dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j-1][1];
}else{
dp[i][j][1]=dp[i-1][j][0];
}
}
}
}
int main(){
int n;
scanf("%d",&n);
DP(110);
while(n--){
int t,ta,tb;
scanf("%d%d%d",&t,&ta,&tb);
cout<<t<<" "<<dp[ta][tb][0]+dp[ta][tb][1]<<endl;
}
return 0;
}
BNU4286——Adjacent Bit Counts——————【dp】
原文：http://www.cnblogs.com/chengsheng/p/4433933.html