首页 > 代码库 > DP 水题
DP 水题
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。
有点数位DP的味道,这个要记得不相邻,但是自己跟自己可以。还有就是枚举的是往前插
dp[i][j] 长i,j打头的个数。又有点递推味道。
#include<algorithm> #include<iostream> #include<iterator> #include<cstdlib> #include<cstring> #include<cstdio> #include<map> #define mem(a) memset(a,0,sizeof(a)) #define inf (1<<30) #define mod 1000000007 using namespace std; typedef long long ll; const int maxn=10+100; ll dp[20][20]; int main() { int k,l; scanf("%d%d",&k,&l); for(int i=0;i<k;i++) dp[1][i]=1; for(int i=2;i<=l;i++) for(int j=1;j<k;j++) { dp[i][j]=dp[i-1][j]; for(int m=0;m<j-1;m++) dp[i][j]+=dp[i-1][m]; for(int m=j+2;m<k;m++) dp[i][j]+=dp[i-1][m]; dp[i][j]%=mod; } ll ans=0; for(int i=1;i<k;i++) ans+=dp[l][i]; if(k<=2) ans=0; cout<<ans<<endl; return 0; }
DP 水题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。