首页 > 代码库 > XDU1160 - 科协的数字游戏I
XDU1160 - 科协的数字游戏I
Description
科协里最近很流行数字游戏。某人命名了一种不降数,这种数字必须满足从左到右各位数字成大于等于的关系,如123,446。现在大家决定玩一个游戏,指定一个整数闭区间[a,b],问这个区间内有多少个不降数。
Input
题目有多组测试数据。每组只含2个数字a, b (1 <= a, b <= 2^31)。
Output
每行给出一个测试数据的答案,即[a, b]之间有多少阶梯数。
Sample Input
1 9 1 19
Sample Output
918
数位DP基础题:
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <string> #include <algorithm> #include <queue> using namespace std; typedef long long ll; int dp[12][12]; vector<int> digit; int a,b; int dfs(int pos,int statu,int done){ if(pos==-1) return 1; if(!done && ~dp[pos][statu]) return dp[pos][statu]; int res = 0; int end = done? digit[pos]:9; for(int i = statu; i <= end ; i++){ res += dfs(pos-1,i,done&&i==end); } if(!done) dp[pos][statu] = res; return res; } ll solve(int num){ memset(dp,-1,sizeof dp); digit.clear(); while(num>0){ digit.push_back(num%10); num /= 10; } return dfs(digit.size()-1,0,1); } int main(){ while(cin >> a >> b){ cout<<solve(b)-solve(a-1)<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。