題目鏈接：

https://acm.bnu.edu.cn/v3/contest_show.php?cid=8506#problem/I

I. Increasing or Decreasing

Case Time Limit: 1000msMemory Limit: 524288KB

題意

求[l,r]上，數(shù)位滿足非遞增獲非遞減的數(shù)的個(gè)數(shù)。

題解

1、dp[i][j][k]表示低i位的第i位為j的，k==1時(shí)表示滿足非遞減，k==2時(shí)滿足非遞增，k==0時(shí)表示每一位都相等。

#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<ctime> #include<vector> #include<cstdio> #include<string> #include<bitset> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> using namespace std; #define X first #define Y second #define mkp make_pair #define lson (o<<1) #define rson ((o<<1)|1) #define mid (l+(r-l)/2) #define sz() size() #define pb(v) push_back(v) #define all(o) (o).begin(),(o).end() #define clr(a,v) memset(a,v,sizeof(a)) #define bug(a) cout<<#a<<" = "<<a<<endl #define rep(i,a,b) for(int i=a;i<(b);i++) #define scf scanf #define prf printftypedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; typedef vector<pair<int,int> > VPII;const int INF=0x3f3f3f3f; const LL INFL=0x3f3f3f3f3f3f3f3fLL; const double eps=1e-8; const double PI = acos(-1.0);//start----------------------------------------------------------------------const int maxn=22;int arr[maxn],tot; ///type根據(jù)dp具體維數(shù)調(diào)整 LL dp[maxn][11][4]; ///ismax標(biāo)記表示前驅(qū)是否是邊界值 ///ser標(biāo)記前驅(qū)是否是前導(dǎo)零 LL dfs(int len,int dig,int type,bool ismax,bool iszer) {if (len == 0) {///遞歸邊界，這說明前驅(qū)都合法了return 1LL;}if (!ismax&&dp[len][dig][type]>=0) return dp[len][dig][type];LL res = 0;int ed = ismax ? arr[len] : 9;///這里插入遞推公式for (int i = 0; i <= ed; i++) {if(i==0&&iszer){///處理前導(dǎo)零res+=dfs(len-1,10,0,ismax&&i==ed,1);}else{if(type==0){if(i==dig||dig==10) res+=dfs(len-1,i,0,ismax&&i==ed,0);else if(i>dig) res+=dfs(len-1,i,1,ismax&&i==ed,0);else if(i<dig) res+=dfs(len-1,i,2,ismax&&i==ed,0);}else if(type==1){if(i>=dig){res+=dfs(len-1,i,type,ismax&&i==ed,0);}}else if(type==2){if(i<=dig){res+=dfs(len-1,i,type,ismax&&i==ed,0);}}}}return ismax ? res : dp[len][dig][type] = res; }LL solve(LL x) {tot = 0;while (x) { arr[++tot] = x % 10; x /= 10; }LL ret=0;return dfs(tot,10,0,true,true); }void init() {clr(dp,-1); }int main() {init();int n; scf("%d",&n);while(n--){LL l,r;scf("%lld%lld",&l,&r);prf("%lld\n",solve(r)-solve(l-1));}return 0; }//end-----------------------------------------------------------------------

2、狀態(tài)和上面差不多，不過是固定k，分別求出來，既ans=非遞增+非遞減-每個(gè)數(shù)位都相同。

#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<ctime> #include<vector> #include<cstdio> #include<string> #include<bitset> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> using namespace std; #define X first #define Y second #define mkp make_pair #define lson (o<<1) #define rson ((o<<1)|1) #define mid (l+(r-l)/2) #define sz() size() #define pb(v) push_back(v) #define all(o) (o).begin(),(o).end() #define clr(a,v) memset(a,v,sizeof(a)) #define bug(a) cout<<#a<<" = "<<a<<endl #define rep(i,a,b) for(int i=a;i<(b);i++) #define scf scanf #define prf printftypedef long long LL; typedef vector<int> VI; typedef pair<int,int> PII; typedef vector<pair<int,int> > VPII;const int INF=0x3f3f3f3f; const LL INFL=0x3f3f3f3f3f3f3f3fLL; const double eps=1e-8; const double PI = acos(-1.0);//start----------------------------------------------------------------------const int maxn=22;int arr[maxn],tot; ///type根據(jù)dp具體維數(shù)調(diào)整 LL dp[maxn][11][4]; ///ismax標(biāo)記表示前驅(qū)是否是邊界值 ///ser標(biāo)記前驅(qū)是否是前導(dǎo)零 LL dfs(int len,int dig,int type,bool ismax,bool iszer) {if (len == 0) {///遞歸邊界，這說明前驅(qū)都合法了return 1LL;}if (!ismax&&dp[len][dig][type]>=0) return dp[len][dig][type];LL res = 0;int ed = ismax ? arr[len] : 9;///這里插入遞推公式for (int i = 0; i <= ed; i++) {if(i==0&&iszer){///處理前導(dǎo)零res+=dfs(len-1,10,type,ismax&&i==ed,true);}else{if(type==1){if(i>=dig||dig==10) res+=dfs(len-1,i,type,ismax&&i==ed,false);}else if(type==2){if(i<=dig||dig==10) res+=dfs(len-1,i,type,ismax&&i==ed,false);}else if(type==0){if(i==dig||dig==10) res+=dfs(len-1,i,type,ismax&&i==ed,false);}}}return ismax ? res : dp[len][dig][type] = res; }LL solve(LL x) {tot = 0;while (x) { arr[++tot] = x % 10; x /= 10; }LL ret=0;ret+=dfs(tot,10,1,true,true);ret+=dfs(tot,10,2,true,true);ret-=dfs(tot,10,0,true,true);return ret; }void init() {clr(dp,-1); }int main() {init();int n; scf("%d",&n);while(n--){LL l,r;scf("%lld%lld",&l,&r);prf("%lld\n",solve(r)-solve(l-1));}return 0; }//end-----------------------------------------------------------------------

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

總結(jié)

以上是生活随笔為你收集整理的BNUOJ 52325 Increasing or Decreasing 数位dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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