難受啊，怎么又遇到我不會的題了（捂臉）

如題，這是一道數(shù)位DP，隨便找了個博客居然就是我們大YZ的……果然nb，然后就是改改模版++注釋就好的了，直接看注釋吧，就是用1~B - 1~A-1而已，枚舉全部位然后判一下是不是上限邊緣和前導(dǎo)零就OK

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; LL bit[20];int len,a[20]; LL as[10],ret[20];//ret表示假如是上限邊緣，后面有多少種填的方式 LL f[20][2][2]; //f[k][fg][z]表示當(dāng)前這個數(shù)x，搞到第k位的時候的數(shù)目 //fg表示該位是不是在上限邊緣 z表示目前是否還是前導(dǎo)零 LL dfs(int x,int k,int fg,int z) {if(k==len+1)return 0;if(f[k][fg][z]!=-1)return f[k][fg][z];LL ans=0;if(fg==1)//如果前面的部分處于上限邊緣 {for(int i=0;i<a[k];i++)//不填上限邊緣，枚舉填什么 {if(z==1&&i==0)ans+=dfs(x,k+1,0,1);else{ans+=dfs(x,k+1,0,0);if(i==x)ans+=bit[len-k];}//如果i是要統(tǒng)計次數(shù)的那個數(shù)字，而且不是在前導(dǎo)零的時候，而且還不是在上限的邊緣//那么后面幾位的數(shù)字有多少種填法x就出現(xiàn)了幾次 }//該位填上限邊緣if(z==1&&a[k]==0)ans+=dfs(x,k+1,1,1);else {ans+=dfs(x,k+1,1,0);if(a[k]==x)ans+=ret[k];}//如果填的是要統(tǒng)計次數(shù)的那個數(shù)字 而且不是在前導(dǎo)零的時候//那么后面的數(shù)字最多有多少種填法x就出現(xiàn)了幾次 }else//沒有限制 {for(int i=0;i<=9;i++)//同上 {if(z==1&&i==0)ans+=dfs(x,k+1,0,1);else {ans+=dfs(x,k+1,0,0);if(i==x)ans+=bit[len-k];}}}f[k][fg][z]=ans;return ans; } char s[20]; void cl()//把A減1 {int t=len;while(t>1&&s[t]=='0'){s[t]='9';t--;}s[t]--;if(s[t]==0){len--;for(int i=1;i<=len;i++)s[i]=s[i+1]-'0';} } int main() {freopen("dream.in","r",stdin);freopen("dream.out","w",stdout);bit[0]=1;for(int i=1;i<=18;i++)bit[i]=bit[i-1]*10;memset(as,0,sizeof(as));scanf("%s",s+1);len=strlen(s+1);cl();for(int i=1;i<=len;i++)a[i]=s[i]-'0';//0的情況，所以填的方案都要+1 ret[len]=1;for(int i=len-1;i>=1;i--)ret[i]=a[i+1]*bit[len-i-1]+ret[i+1];for(int i=0;i<=9;i++){memset(f,-1,sizeof(f));as[i]-=dfs(i,1,1,1);}scanf("%s",s+1);len=strlen(s+1);for(int i=1;i<=len;i++)a[i]=s[i]-'0';ret[len]=1;for(int i=len-1;i>=1;i--)ret[i]=a[i+1]*bit[len-i-1]+ret[i+1];for(int i=0;i<=9;i++){memset(f,-1,sizeof(f));as[i]+=dfs(i,1,1,1);}for(int i=0;i<9;i++)printf("%d ",as[i]);printf("%d\n",as[9]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/AKCqhzdy/p/7716156.html

總結(jié)

以上是生活随笔為你收集整理的bzoj1833: [ZJOI2010]count 数字计数USACO37 Cow Queueing 数数的梦（数位DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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