要求找出范圍內含有“13”且能被13整除的數字的個數

可以使用數位dp

dp[i][j][0] 表示長度為i，余數為j，不含13的數字的個數

dp[i][j][1] 表示長度為i，余數為j，3開頭的數字的個數

dp[i][j][2] 表示長度為i，余數為j，含有"13"的數字的個數

index[1] = 1;

for(i=2; i<11; ++i)

　　index[i] = (index[i-1] * 10) % 13;

index[i] 存儲的為1,10,100,1000,10000 % 13 的余數

那么，狀態轉移方程詳見源代碼

1 #include <stdio.h> 2 int dp[11][13][3]; 3 int index[11]; 4 int num[11]; 5 void init() 6 { 7 int i,j,k; 8 index[1] = 1; 9 for(i=2; i<11; ++i) 10 index[i] = (index[i-1]*10) % 13; 11 dp[0][0][0] = 1; 12 for(i=1; i<11; ++i) 13 { 14 for(k=0; k<13; ++k) 15 { 16 //（1） 17 dp[i][(index[i]+k)%13][0] -= dp[i-1][k][1]; 18 //長度為i-1,余數為k的不含13的數字前面加上3,-->長度為i-1，余數為k的3開頭的個數 19 dp[i][(index[i]*3+k)%13][1] += dp[i-1][k][0]; 20 //長度為i-1，余數為k的3開頭的數字前面加上1-->長度為i，余數為(index[i]+k)%13含13的數字個數 21 dp[i][(index[i]+k)%13][2] += dp[i-1][k][1]; 22 for(j=0; j<10; ++j) 23 { 24 //長度為i-1，余數為k的不含13的數字前面加上j-->長度為i，余數為(index[i]*j+k)%13不含13的數字個數 25 //但是dp[i-1][k][0] 里面是包含dp[i-1][k][1]的，當加上數字1時，成為了含有13的數字，這里多加，所以在（1）處減去 26 dp[i][(index[i]*j+k)%13][0] += dp[i-1][k][0]; 27 //長度為i-1，余數為k的含13的數字前面加上j-->長度為i，余數為(index[i]*j+k)%13含13的數字個數 28 dp[i][(index[i]*j+k)%13][2] += dp[i-1][k][2]; 29 } 30 } 31 } 32 } 33 int getAns(int n) 34 { 35 int i,j,k,len=0,ans=0; 36 while(n) 37 { 38 num[++len] = n % 10; 39 n /= 10; 40 } 41 num[len+1] = 0; 42 bool flag = false; 43 int t = 0,mod; 44 for(i=len; i>=1; --i) 45 { 46 for(k=0; k<13; ++k) 47 { 48 if(num[i]>1 && !flag)//第i位取1 49 { 50 mod = (index[i]+k+t)%13;//第i位取1時余數為mod 51 if(mod==0) ans += dp[i-1][k][1];//如果余數為0，那么就加上3開頭的數字個數 52 } 53 if(num[i+1]==1 && num[i]>3 &&!flag)//第i+1位為1，第i位取3. 54 { 55 mod = (t + k) % 13;//第i+1位為1，第i位取3的余數為mod 56 if(mod==0) ans += dp[i][k][1];//如果余數為0，那么就加上3開頭的數字個數 57 } 58 for(j=0; j<num[i]; ++j)//第i位為j時， 59 { 60 mod = (index[i]*j+k+t)%13;//第i位為j時余數為mod 61 if(mod==0) ans += dp[i-1][k][2];//如果余數為0，那么就加上含有13的數字的個數 62 if(mod==0 && flag) ans += dp[i-1][k][0];//如果余數為0，且前面的數字含有13，那么就加上不含13的數字個數 63 } 64 } 65 t = (t + num[i]*index[i])%13;//第len位到第i位的數字固定后產生的余數 66 if(num[i+1]==1 && num[i]==3) 67 flag = true; 68 } 69 return ans; 70 } 71 int main() 72 { 73 int n; 74 init(); 75 76 while(scanf("%d",&n)!=EOF) 77 { 78 printf("%d\n",getAns(n+1)); 79 } 80 return 0; 81 } View Code

數位dp的難點就在于狀態的轉移，還有統計。

關鍵要弄懂它統計的原理。

http://www.cnblogs.com/justPassBy/p/4275226.html

轉載于:https://www.cnblogs.com/justPassBy/p/4277263.html

總結

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

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