傳送門

?

參考博文：

　　[1]:http://www.voidcn.com/article/p-drrnjrmy-wm.html

?

題意：

　　找出區間內數中含有13的并且能被13整除的數的個數

題解：

　　搜了好多博客，看到了一些關鍵詞；

　　其中一個就有"秦九韶算法"，補了補秦九韶算法，再看一下參考博文的代碼，感覺，和秦九韶算法關聯不是太大；

　　下面說說我的思路：

　　假設 num = 121394 ，（num%13=0，且含有"13"）

　　num可寫成 1*10⁵+2*10⁴+1*10³+3*10²+9*10¹+4;

　　那么，將這個數任意拆分成兩部分，例如 令 a =?1*10⁵+2*10^4?, b=1*10³+3*10²+9*10¹+4;

　　你會發現 a%13+b%13 = 13；

　　(假設下標從0開始，最高為為 pos，從第 i 位置斷開，[i+1,pos]組成的數為 a)

　　那么，定義 dp[ i ][ j ][ k ]:

　　dp[ i ][ j ][0]表示從pos到i+1位不含有"13"且 j =?(13-a%13)的數的個數；

　　dp[?i ][?j ][1]表示從pos到i+1位不含有"13"但是第i+1位是1且 j = (13-a%13)的數的個數 ；

　　dp[ i ][ j ][2]表示從pos到i+1為含有"13"且 j =??(13-a%13) 的數的個數；

AC代碼：

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 7 int n; 8 int digit[10]; 9 int dp[10][13][3]; 10 11 int quickPower(int a,int b) 12 { 13 int ans=1; 14 while(b) 15 { 16 if(b&1) 17 ans *= a; 18 a *= a; 19 b >>= 1; 20 } 21 return ans; 22 } 23 //s對應著0,1,2狀態 24 int DFS(int curPos,int curNum,int s,bool limit) 25 { 26 if(curPos == -1) 27 return curNum%13 == 0 && s == 2 ? 1:0; 28 29 //以 num = 121394 為例 30 //如果當前的 curPos 來到 3數字處，那么 curNum = 121 31 //而實際要算的是 13-121000%13，所以需要將curNum*1000，就是對應的quickPower() 32 int mod=13-curNum*quickPower(10,curPos+1)%13; 33 if(!limit&&dp[curPos][mod][s] != -1) 34 return dp[curPos][mod][s]; 35 36 int up=limit ? digit[curPos]:9; 37 int ans=0; 38 for(int i=0;i <= up;++i) 39 { 40 int t=0; 41 if(s == 2) 42 t=2; 43 else if(s == 1 && i == 3) 44 t=2; 45 else if(i == 1) 46 t=1; 47 ans += DFS(curPos-1,curNum*10+i,t,limit&&i==digit[curPos]); 48 } 49 if(!limit) 50 dp[curPos][mod][s]=ans; 51 52 return ans; 53 } 54 int Solve(int x) 55 { 56 int k=0; 57 while(x) 58 { 59 digit[k++]=x%10; 60 x /= 10; 61 } 62 return DFS(k-1,0,0,true); 63 } 64 int main() 65 { 66 mem(dp,-1); 67 while(~scanf("%d",&n)) 68 printf("%d\n",Solve(n)); 69 70 return 0; 71 } View Code

?

轉載于:https://www.cnblogs.com/violet-acmer/p/10619430.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的hdu 3652 B-number（数位DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。