首页 > 代码库 > ural 1009
ural 1009
我们定义一个合法的K进制数为一个不含连续两个零的K进制数。
例如：
1010230 是一个合法的7位数。
1000198 不是合法的数。
0001234 不是7位数，是一个合法的4位数。
给你N,和K,求出N位的K进制数的总数。
2 <= K <= 10; N >= 2; 4 <= N+K <= 18。
/*DP,f[i]代表第i位置 可以表示成的数字的种类, f[i]:=(k-1)*(f[i-1]+f[i-2]) //f[0]:=1,f[1]:=k-1*/ #include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>#include<vector>#include<cstdlib>#include<cmath>#include<queue>using namespace std;int n,k,dp[50];int main(){while(scanf("%d%d",&n,&k)!=EOF){k--; dp[0]=1;dp[1]=k;for(int i=2;i<=n;i++)dp[i]=k*(dp[i-1]+dp[i-2]);printf("%d\n",dp[n]);}return 0;}
ural 1009
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。