页面看不到网站,网站开发合同知识产权,惠州城乡和住房建设局网站,公司网站怎么做网站备案Acwing 1082. 数字游戏
题意#xff1a;
现在大家决定玩一个游戏#xff0c;指定一个整数闭区间 [a,b]#xff0c;问这个区间内有多少个不降数。
题解#xff1a;
利用数位dp的套路来做 我们还是利用前缀和来做 我们先求1~n中满足情况的个数 对于一个n位数#xff0c;…Acwing 1082. 数字游戏
题意
现在大家决定玩一个游戏指定一个整数闭区间 [a,b]问这个区间内有多少个不降数。
题解
利用数位dp的套路来做 我们还是利用前缀和来做 我们先求1~n中满足情况的个数 对于一个n位数我们将其每一位用vector存an-1 ~ a0,我们从高位到低位开始一位一位考虑对于第an-1位,我们有两种考虑情况一个是填0 ~ an-1-1,另一个是填an-1对于第一个情况往往是可以直接求出来的利用组合数或者dp可以求出在本题中我们用dp来求第一个情况 对于第一个情况如果我们当前考虑的是第i位如果我们填j按照题目要求递增关系第i-1位应该填j~9.每一位的填写只于上一位的最大值有关 我们设dp[i][j]表示最高位是j一共有i位要填满足非递减的数的数量 所以有dp[i][j]Σdp[i-1][j~9]
这样我们解决了第一个情况左侧第二个情况右侧的话我们可以再分解考虑下一位第an-2的填写情况一直这样到最后一位。注意填写情况要满足题目要求的非递减要求所以我们要用last来保存一次的数这样下一次填的数必须大于等于last否则就break如果能顺利走到底最后一位说明满足情况tot
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn15;
int f[maxn][maxn];
void init(){for(int i0;i9;i)f[1][i]1;for(int i2;imaxn;i){for(int j0;j9;j){for(int kj;k9;k){f[i][j]f[i-1][k];}}}
}
int solve(int n){if(!n)return 1;vectorintvec;while(n)vec.push_back(n%10),n/10;int res0;int last0;for(int ivec.size()-1;i0;i--){int xvec[i];for(int jlast;jx;j){resf[i1][j];//还剩i1位 }if(xlast)break;lastx;if(!i)res;}return res;
}
int main()
{init(); int l,r;while(cinlr){coutsolve(r)-solve(l-1)endl;}return 0;
}
