题意 ：给你一串由1和0组成的长度为n的数串a1,a2,a3,a4.....an，定义一个操作为AdjBC(a) = a1*a2+a2*a3+a3*a4+....+an-1*an。输入两个数m和k，要求输出满足长度为m的数串进行上述操作能够得到的结果为k的个数。
思路 : 典型DP，列出状态转移方程就行了。dp[i][j][0]代表长度前 i 的数串和为 j 并且当前位置为0.
dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j-1][1];
dp[i][j][0]=dp[i-1][j][1]+dp[i-1][j][0];
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; int dp[110][110][2]; void chart() { dp[1][0][0]=dp[1][0][1]=1; for(int i = 2 ; i <= 100 ; 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 j = 1 ; j < 100 ; j++) for(int i = 2 ; i <= 100 ; i++) { dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j-1][1]; dp[i][j][0]=dp[i-1][j][1]+dp[i-1][j][0]; } } int main() { int n, cas, m, k; chart() ; scanf("%d", &n); while (n--) { scanf("%d %d %d", &cas, &m, &k); printf("%d %d\n",cas, dp[m][k][0]+dp[m][k][1]); } return 0; }
还有一位大神用二维写的，这里
POJ 3786 Adjacent Bit Counts (DP),布布扣,bubuko.com
POJ 3786 Adjacent Bit Counts (DP)
原文：http://www.cnblogs.com/luyingfeng/p/3644281.html
