POJ 3208 Apocalypse Someday(数位dp)

开发技术 作者: 2024-06-16 23:50:01
题意:输出第n个包含连续三个6的数思路:dp[i][0]表示i位数中首位不为6且不含666的数的数量dp[i][1]表示i位数中首位连续1个6并且不含666的数的数量dp[i][2]表示i位数中首位连续2个6并且不含666的数的数量dp[i][3]表示i位数中含有666的数的数量写出递推关系即可,再

题意:输出第n个包括连续3个6的数

思路:

dp[i][0]表示i位数中首位不为6且不含666的数的数量
dp[i][1]表示i位数中首位连续1个6并且不含666的数的数量
dp[i][2]表示i位数中首位连续2个6并且不含666的数的数量
dp[i][3]表示i位数中含有666的数的数量

写出递推关系便可,再肯定出带求的数有多少位,再从高位到低位逐次肯定

//132K 16MS #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; ll dp[15][4]; const int trans[4][10]={ {0,0},{3,3,3},1,2,3} }; int main(){ dp[0][0]=1; for(int i=1;i<=15;i++){ dp[i][0]=(dp[i⑴][0]+dp[i⑴][1]+dp[i⑴][2])*9; dp[i][1]=dp[i⑴][0]; dp[i][2]=dp[i⑴][1]; dp[i][3]=dp[i⑴][3]*10+dp[i⑴][2]; } int T; scanf("%d",&T); while(T--){ ll n; scanf("%I64d",&n); int dig=0; int cur=3; while(dp[dig][3]<n) dig++; while(dig){ ll s=0; for(int i=0;i<10;i++){ ll tmps=0; for(int j=3;j>=trans[cur][i];j--){ tmps+=dp[dig⑴][j]; } if(s+tmps>=n){ printf("%d",i); cur=trans[cur][i]; break; } s+=tmps; } n-=s; dig--; } putchar(' '); } return 0; }



原创声明
本站部分文章基于互联网的整理,我们会把真正“有用/优质”的文章整理提供给各位开发者。本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
本文链接:http://www.jiecseo.com/news/show_28343.html