poj 3208--Apocalypse Someday(数位dp)

传送门

解题思路

首先刷出一个20位的表，这样利于后面的操作。设$f[i][j]$为填到第$i$位，目前后$j$位为6的个数，当$j=3$时就是已经满足条件。那么$f[i+1][j+1]+=f[i][j] ，f[i+1][0]+=f[i][j]*9 f[i+1][3]+=f[i][j]*10$，这个方程比较好理解。然后对于每个询问用试填法，需要记录已经填过的数字中是否有3个6，还要记录最后几位有几个6。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>

using namespace std;
const int MAXN = 25;
typedef long long LL;

inline LL rd(){
    LL x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x;
}

LL f[MAXN][5],n;
int T;

int main(){
    f[0][0]=1;
    for(int i=0;i<20;i++){
        for(int k=0;k<3;k++){
            f[i+1][k+1]+=f[i][k];
            f[i+1][0]+=f[i][k]*9;            
        }
        f[i+1][3]+=f[i][3]*10;
    }
    cin>>T;
    while(T--){
        n=rd();int m;
        for(m=3;f[m][3]<n;m++);
        for(int i=m,k=0;i;i--)
            for(int j=0;j<=9;j++){
                LL cnt=f[i-1][3];
                if(j==6 || k==3) 
                    for(int oo=max(0,3-k-(j==6));oo<3;oo++)
                        cnt+=f[i-1][oo];
                if(cnt<n) n-=cnt;
                else {
                    if(k<3) k=j==6?k+1:0;
                    printf("%d",j);
                    break;
                }
            }
        putchar('
');
    }
    return 0;
}