題意：求區(qū)間[l,r]內(nèi)有多少個(gè)數(shù)符合，這個(gè)數(shù)的任意的相鄰k位數(shù)(digits)，這k個(gè)數(shù)都兩兩不相等

l,r范圍是1~1e18,k是2~5

思路：數(shù)位DP，因?yàn)镵<=5，我們最多需要保存下來當(dāng)前位的前4位就足夠了。因?yàn)閐p[pos][p1][p2][p3][p4]表示，現(xiàn)在枚舉取第pos位，pos位之前的四位分別為p1,p2,p3,p4,p4是pos的上一位。那么p1~p4的范圍就是0~9，但是因?yàn)榭偽粩?shù)小于當(dāng)前數(shù)字的位數(shù)的數(shù)也要進(jìn)行枚舉，需要一個(gè)數(shù)字來區(qū)分它是前導(dǎo)0還是在中間時(shí)為0，令p = 10是前導(dǎo)0，或者表示不需要儲(chǔ)存，即最高位的前幾位。那么dfs函數(shù)可以寫成?dfs( int pos , int p1 , int p2 , int p3 , int p4 , bool flag ) flag表示pos位能否取到全部的數(shù)位(0~9)還是會(huì)受到前面最高位的影響只能取一部分。

對于記憶化搜索首先明確代碼的dfs的定義為當(dāng)前四位分別為p1,p2,p3,p4時(shí)枚舉第pos位總共有多少種方法，則dp方程很容易便能想到是1、pos位之前都取的0，即p4==10，而pos位也取0，一直都是前導(dǎo)零。2、而當(dāng)p4!=10，pos位取的i去和p判斷一下有沒有重復(fù)(根據(jù)k來判斷需要比較幾個(gè)p)，所以也是可以向下統(tǒng)計(jì)的，然后記得記憶化就好。

而dp的定義為當(dāng)前四位數(shù)為p1,p2,p3,p4是枚舉pos位總共有多少種方法，這與dfs是不同的，因?yàn)閷τ赿p 不需要考慮必須在小于當(dāng)前數(shù)的范圍內(nèi)進(jìn)行枚舉，而dfs代表的方法數(shù)必須在小于當(dāng)前數(shù)的范圍之內(nèi)，這就可以解釋第38行。同時(shí)因?yàn)榇蠖鄶?shù)情況下都是flag為假，隨意選擇記憶這種情況可以降低復(fù)雜度(這是我猜的，如果大家有別的想法可以說出來交流一下)

#include #include#include#include#include#include#include

using namespacestd;

typedeflong longll;const int N = 50000+10;const int mod=1e9+7;const double en=2.718281828459;

ll l,r,dp[20][11][11][11][11];int k,dig[20];bool cek(int u,int p1,int p2,int p3,intp4){if(k==2)return u!=p4;if(k==3)return u!=p4&&u!=p3;if(k==4)return u!=p4&&u!=p3&&u!=p2;if(k==5)return u!=p4&&u!=p3&&u!=p2&&u!=p1;

}

ll dfs(int pos,int p1,int p2,int p3,int p4,intflag){if(pos==0)return p4!=10;if(!flag&&dp[pos][p1][p2][p3][p4]!=-1) returndp[pos][p1][p2][p3][p4];//記憶化int ed=flag?dig[pos]:9;//當(dāng)前面的數(shù)取小于其位置上的數(shù)顯然后面的數(shù)可以取0~9

ll ans=0;for(int i=0;i<=ed;i++){if(i==0&&p4==10)

ans+=dfs(pos-1,10,10,10,10,flag&&i==ed);else if(cek(i,p1,p2,p3,p4))

ans+=dfs(pos-1,p2,p3,p4,i,flag&&i==ed);

}if(!flag) dp[pos][p1][p2][p3][p4]=ans;returnans;

}

ll cal(ll u){int cnt=0;while(u>0){

dig[++cnt]=u%10;

u/=10;

}return dfs(cnt,10,10,10,10,1);

}intmain()

{//freopen("in.txt", "r", stdin);

while(~scanf("%lld %lld %d",&l,&r,&k)){

memset(dp,-1,sizeof(dp));

printf("%lld\n",cal(r)-cal(l-1));

}return 0;

}

總結(jié)

以上是生活随笔為你收集整理的数位dp 记忆化搜索java_hdu 5787 数位dp,记忆化搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。