NYOJAdjacentBitCounts（DP）

AdjacentBitCounts

时间限制: 1000ms 内存限制: 128000KB 64位整型:      Java 类名: 上一题   提交   运行结果   统计   讨论版   下一题

类型:      lv.2   没有 难度     lv.1      lv.2     lv.3     lv.4      lv.5     lv.6      lv.7     lv.8     lv.9      lv.10 搜索  数据结构 动态规划 STL练习  高精度计算 图论 几何  数学 矩阵计算 入门题目  字符串 博弈论                   添加

题目描述

For astring of n bits x1, x2, x3, …, xn,  theadjacent bit count of the string  isgiven by     fun(x) = x1*x2 + x2*x3 + x3*x 4 + … + xn-1*x n which counts the number of times a 1 bit is adjacent to another 1 bit. Forexample:  

     Fun(011101101) = 3

     Fun(111101101) = 4

     Fun (010101010) = 0

Write a program which takes asinput integers n and p and returns the number of bit stringsx of n bits (out of 2ⁿ) that satisfy  Fun(x)= p.

 

Forexample, for 5 bit strings, there are 6 ways of getting fun(x) = 2:

11100,01110, 00111, 10111, 11101, 11011

输入

On the first line of the input is a single positive integer k, telling the number of test cases to follow. 1 ≤ k ≤ 10 Each case is a single line that contains a decimal integer giving the number (n) of bits in the bit strings, followed by a single space, followed by a decimal integer (p) giving the desired adjacent bit count. 1 ≤ n , p ≤ 100

输出

For each test case, output a line with the number of n-bit strings with adjacent bit count equal to p.

样例输入

2 5 2 20 8

样例输出

6 63426

题意：x是有0或1组合的数组 ， fun(x) = x1*x2 + x2*x3 + x3*x 4 + … + xn-1*x n   求位数为N，FUN值为P的组合有多少种。

分析：简单dp 递推就行了

代码：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <queue> #define mem(p,k) memset(p,k,sizeof(p)); #define rep(i,j,k) for(int i=j; i<k; i++) #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define inf 0x6fffffff #define ll long long using namespace std; const int mod=1e9+7; int n,m,k,cur,x,y; ll minn,maxx; int nex[4][2]={0,1,1,0,0,-1,-1,0}; int dp[110][110][2]; int main(){ int t; cin>>t; while(t--){ cin>>n>>m; mem(dp,0); dp[2][0][0]=2;dp[2][0][1]=1;dp[2][1][1]=1;dp[2][1][0]=0; for(int i=3;i<=n;i++){ for(int j=0;j<=min(m,i-1);j++){ dp[i][j][1]+=dp[i-1][j-1][1]+dp[i-1][j][0]; dp[i][j][0]+=dp[i-1][j][0]+dp[i-1][j][1]; } } cout<<dp[n][m][0]+dp[n][m][1]<<endl; } return 0; }