正題

---

大意

如果一個數(shù)每一位都小于k那么這個數(shù)是好數(shù)。給出n和k，求1-n里有多少個好數(shù)。

---

解題思路1

將起改為一個k+1進制的數(shù)，那么每次加1后這個數(shù)都是好數(shù)。然后判斷一下是否大于n（十進制的情況下）

解題思路2

數(shù)位dp，時間復(fù)雜度O(n的位數(shù))：
f[i]表示后i位數(shù)沒有被前面的數(shù)影響的好數(shù)數(shù)量
g[i]表示后i位數(shù)被前面的數(shù)影響的好數(shù)數(shù)量
n[i]表示n的第i位數(shù)
然后動態(tài)轉(zhuǎn)移方程

f[i]=f[i?1]?(k+1)f[i]=f[i?1]?(k+1)
g[i]=f[i](n[i]>k)g[i]=f[i](n[i]>k)
g[i]=g[i?1]+f[i?1]?n[i](n[i]<=k)g[i]=g[i?1]+f[i?1]?n[i](n[i]<=k)

---

代碼1

#include<cstdio> using namespace std; int a[9],maxs[9],w,m,s,n; bool add() {bool flag=0;a[1]++;//加1for (int i=1;i<=w;i++){if (a[i]>m){a[i+1]++;a[i]=0;//進位}if (a[i]>maxs[i]) flag=true;else if (a[i]<maxs[i]) flag=false;//判斷大小}if (a[w+1]!=0) return true;return flag; } int main() { scanf("%d%d",&n,&m);a[1]=0;for (int i=n;i;i/=10){maxs[++w]=i%10;//計算}while (true){if (add()) break;s++;}printf("%d",s); }

代碼2

#include<cstdio> using namespace std; int n,num,g,f,k; int main() {scanf("%d%d",&n,&k);f=1;g=1;for (n=n;n;n/=10){num=n%10;if (num>k) g=(k+1)*f;else g+=num*f;f=(k+1)*f;//動態(tài)轉(zhuǎn)移}printf("%d",g-1); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的【2018.4.7】模拟赛之一-ssl2382 K好数【数位dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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