Adjacent Bit Counts(动态规划 三维的)
Adjacent Bit Counts(动态规划 三维的)
1944864971 发表于2年前
Adjacent Bit Counts(动态规划 三维的)
  • 发表于 2年前
  • 阅读 8
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

/**
题意:
给出一个01串 按照题目要求可以求出Fun(X)的值
比如: 111 Fun(111)的值是2;
输入:
t (t组测试数据)
n k (有n位01串 Fun()的值为K)

输出:有多少种组合 使得这n位01串的Fun()值为k;

分析:
动态规划
转移方程 dp[i][j][k] i代表01串的长度 j代表Fun()的值(或者说是权重) k代表最后一位是0还是1
在已知的01串后面加一个0 添加前后的权值不会发生变化 即dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
在已知的01串后面加一个1 如果没有添加之前的最后一位是1的话 添加之后的权值是j 那么添加之前的值是j-1
如果没有添加之前的最后一位是0的话 添加之后的权值是j 那么添加之前的值仍是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];


初始化很重要

*/

include

include

include

using namespace std;
int dp[105][105][2];
int main()
{
dp[1][0][0]=1;
dp[1][0][1]=1;
for(int i=2; i<=105; i++)
{
dp[i][0][0]=dp[i-1][0][0]+dp[i-1][0][1];
dp[i][0][1]=dp[i-1][0][0];
}
for(int i=2; i<=105; i++)
for(int j=1; j<i; 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;
scanf("%d",&t);

while(t--)
{
    int n,k;
    scanf("%d%d",&n,&k);
    printf("%d\n",dp[n][k][1]+dp[n][k][0]);
}

return 0;

}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: