POJ 3786 Adjacent Bit Counts (DP)

点我看题目

题意 ：给你一串由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;
}

还有一位大神用二维写的，这里