poj 3208 Apocalypse Someday 自动机+dp

题意：

求第n个包含3个连续6的数。

分析：

设状态0表示末尾没有6，状态1表示末尾有1个6，状态2表示末尾有2个6，状态3表示末尾有3个6或之前有3个6，可构造出确定状态自动机。然后对该自动机进行dp,a[i][j]表示位于自动机的j状态，再走i步，能包括含3个6的数的个数。之后再用数位dp的思想由高位至低位确定最终答案每位上的数。这和AC自动机是有区别的，需好好体会。

代码：

//poj 3208
//sep9
#include <iostream>
using namespace std;
typedef long long LL;
const int maxN=16;
int s[4][12];
LL a[maxN][4],n;

int main()
{
	memset(s,0,sizeof(s));
	memset(a,0,sizeof(a));
	s[0][6]=1;
	s[1][6]=2;
	s[2][6]=3;
	int i,j,k;
	for(i=0;i<10;++i)
		s[3][i]=3;	
	a[0][3]=1;
	for(i=1;i<maxN;++i)
		for(j=0;j<4;++j)
			for(k=0;k<10;++k)
				a[i][j]+=a[i-1][s[j][k]];	
	int T;
	scanf("%d",&T);
	while(T--){
		int w;
		scanf("%lld",&n);
		for(w=0;w<maxN;++w)
			if(a[w][0]>=n)	
				break;
		int state=0;
		LL ans=0;
		while(w--){
			LL tmp=0;
			for(i=0;i<10;++i){
				tmp+=a[w][s[state][i]];
				if(tmp>=n){
					n-=tmp-a[w][s[state][i]];
					state=s[state][i];
					ans=10*ans+i;
					break;
				}		
			}	
		}
		printf("%lld\n",ans);
	}	
	return 0;	
} 

poj 3208 Apocalypse Someday 自动机+dp

原文：http://blog.csdn.net/sepnine/article/details/44619457