蓝桥k好数

本文主要是介绍蓝桥k好数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

如题：http://lx.lanqiao.org/problem.page?gpid=T13

问题描述

 

 

思路：如果暴力，每一位范围0-k，一共l位，就是O(l^k)，最大100^100，肯定超。

观察，相邻的2位只要不大小不相邻，于是从i-1位数一定可以推出i位数字的情况，

dp[i][j]表示i位数字且第一位是j的所有情况。

dp[i][j]=sum(dp[i-1][x])    (x∈[0,k))\   i∈[2,l]    j∈[0,k)

为什么这个地方j可以等于0

现实中是不可能出现首位是0这种情况的，但是在递推的过程中会用到.除了第一位其余位可以为0

 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 1000000007
int k,l;
int dp[105][105];

int main()
{
 cin>>k>>l;
 int i,j,x;
 for(i=0;i<k;i++)
  dp[1][i]=1;
 for(i=2;i<=l;i++)
  for(j=0;j<k;j++)
   for(x=0;x<k;x++)
   {
    if(x!=j-1&&x!=j+1)
    {
      dp[i][j]+=dp[i-1][x];
      dp[i][j]%=MOD;
    }
   }
   int sum=0;
 for(i=1;i<k;i++)
 {
  sum+=dp[l][i];
  sum%=MOD;
 }
 cout<<sum<<endl;
}

 

 

这篇关于蓝桥k好数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---