Acwing 1082. 數字游戲

題意：

現在大家決定玩一個游戲，指定一個整數閉區間 [a,b]，問這個區間內有多少個不降數。

題解：

利用數位dp的套路來做
我們還是利用前綴和來做
我們先求1~n中滿足情況的個數
對于一個n位數，我們將其每一位用vector存（a_n-1 ~ a₀）,我們從高位到低位開始一位一位考慮，對于第a_n-1位,我們有兩種考慮情況，一個是填0 ~ a_n-1-1,另一個是填a_n-1，對于第一個情況，往往是可以直接求出來的，利用組合數或者dp可以求出，在本題中，我們用dp來求第一個情況

對于第一個情況，如果我們當前考慮的是第i位，如果我們填j，按照題目要求，遞增關系，第i-1位應該填j~9.每一位的填寫，只于上一位的最大值有關
我們設dp[i][j]表示最高位是j，一共有i位要填，滿足非遞減的數的數量
所以有dp[i][j]=Σdp[i-1][j~9]

這樣我們解決了第一個情況（左側），第二個情況（右側）的話，我們可以再分解，考慮下一位第a_n-2的填寫情況，一直這樣到最后一位。注意填寫情況要滿足題目要求的非遞減要求，所以我們要用last來保存一次的數，這樣下一次填的數必須大于等于last，否則就break，如果能順利走到底（最后一位），說明滿足情況，tot++

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=15; int f[maxn][maxn]; void init(){for(int i=0;i<=9;i++)f[1][i]=1;for(int i=2;i<maxn;i++){for(int j=0;j<=9;j++){for(int k=j;k<=9;k++){f[i][j]+=f[i-1][k];}}} } int solve(int n){if(!n)return 1;vector<int>vec;while(n)vec.push_back(n%10),n/=10;int res=0;int last=0;for(int i=vec.size()-1;i>=0;i--){int x=vec[i];for(int j=last;j<x;j++){res+=f[i+1][j];//還剩i+1位 }if(x<last)break;last=x;if(!i)res++;}return res; } int main() {init(); int l,r;while(cin>>l>>r){cout<<solve(r)-solve(l-1)<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的Acwing 1082. 数字游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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