程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4518 ac自動機+數位dp

HDU 4518 ac自動機+數位dp

編輯：C++入門知識

HDU 4518 ac自動機+數位dp

吉哥系列故事——最終數

Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 304 Accepted Submission(s): 102

Problem Description 　　在2012年騰訊編程馬拉松比賽中，吉哥解決了一道關於斐波那契的題目，這讓他非常高興，也更加燃起了它對數學特別是斐波那契數的熱愛。現在，它又在思考一個關於斐波那契的問題：
　　假如我們現在已知斐波那契數是1，1，2，3，5，8，13，21，34，55，89...
　　由於吉哥特別喜歡斐波那契數，它希望每個數中都包含斐波那契數，比如說130，其中包含了13，或者5534包含了55和34，只要數位中含有至少一個斐波那契數就是吉哥想要的數。但是這種數實在太多了，於是它去掉那些僅僅含有小於10的斐波那契數的數，比如說1，僅僅含有1，所以被去掉；或者335只含有3和5，都是小於10的斐波那契數，所以也去掉；但是131是留下的，因為它含有13，我們暫且稱這類數為F數,不難得到前幾個F數是 13 ，21， 34， 55， 89，113，121，130，131...
　　霸氣的吉哥覺得這樣還不夠，它想將斐波那契進行到底——在前面F數的基礎上，吉哥要得到那些是第斐波那契數個的F數！就是說，我們假設F數從1開始標號，那麼13是第1個F數，吉哥想要那些在F數中的排列或者說下標也要是斐波那契數的數，吉哥稱之為最終數，如13，21，34，89，130...
　　現在給你一個數n，吉哥想知道離n最近的最終數與n的差的絕對值是多少。

Input 　　輸入包含多組測試數據。
　　每組測試數據包含一個整數n ( 1 <= n <= 10^11)；
　　若n = -1，表示輸入結束。

Output 　　對於每個n，請輸出離n最近的最終數與n的差的絕對值。
Sample Input

1
100
-1

Sample Output

12
11

Source 2013騰訊編程馬拉松初賽第三場（3月23日）

把斐波那契數列插入ac自動機，然後數位dp進行二分查找，

代碼：

/* ***********************************************
Author :rabbit
Created Time :2014/8/15 16:27:37
File Name :3.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct Trie{
	ll next[1010][10],end[1010],fail[1010];
	ll root,L;
	void init(){
		L=0;
		root=newnode();
	}
	ll newnode(){
		for(ll i=0;i<10;i++)
			next[L][i]=-1;
		end[L++]=0;
		return L-1;
	}
	void insert(ll x){
		ll a[15],len=0;
		while(x){
			a[len++]=x%10;
			x/=10;
		}
		//for(ll i=len-1;i>=0;i--)cout<=0;i--){
			if(next[now][a[i]]==-1)
				next[now][a[i]]=newnode();
			now=next[now][a[i]];
		}
		end[now]=1;
	}
	void build(){
		queue Q;
		fail[root]=root;
		for(ll i=0;i<10;i++)
			if(next[root][i]==-1)
				next[root][i]=root;
			else{
				fail[next[root][i]]=root;
				Q.push(next[root][i]);
			}
		while(!Q.empty()){
			ll now=Q.front();
			Q.pop();
			end[now]|=end[fail[now]];
			for(ll i=0;i<10;i++)
				if(next[now][i]==-1)
					next[now][i]=next[fail[now]][i];
				else{
					fail[next[now][i]]=next[fail[now]][i];
					Q.push(next[now][i]);
				}
		}
	}
}ac;
ll fib[60],dp[15][1010],seq[60],POW[20];
ll suf[15],num[15];
ll dfs(ll pos,ll st,bool flag){
	if(pos==0)return 0;
	if(flag&&dp[pos][st]!=-1)return dp[pos][st];
	ll u=flag?9:num[pos];
	ll ans=0;
	for(ll i=0;i<=u;i++){
		ll state=ac.next[st][i];
		if(ac.end[state]){
			if(flag||i10)ac.insert(fib[i]);
	 POW[0]=1;
	 for(ll i=1;i<=15;i++)POW[i]=10*POW[i-1];
	 ac.build();
     for(ll i=2;i<=56;i++){
		 ll l=13,r=POW[12];
		 while(l>n&&n!=-1){
			ll ans=1e15;
			 for(ll i=2;i<=56;i++){
				 ll tt=n-seq[i];
				 if(tt<0)tt=-tt;
				 ans=min(ans,tt);
			 }
			 cout<