本文主要是介绍Mountain Number FZU - 2109(数位DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Mountain Number
题目链接: FZU - 2109
题意:若一个数他的奇数位大于等于与他相邻的偶数为, 则称之为Mountain Number, L~R有几个这样的数;
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
int dp[15][15][2];//dp[pre][last][odd];
int digit[15];
int dfs(int pre, int last, int odd, int zero, int limit){//pre:当前位数; last:上一位的数; odd=1:当前位为奇数位,反之为偶数位; zero=0:无前导零;if(pre==-1) return 1;if(!limit&&dp[pre][last][odd]!=-1) return dp[pre][last][odd];int up=limit?digit[pre]:9;int ans=0;for(int i=0; i<=up; i++){if(zero==0&&i==0) ans+=dfs(pre-1, 9, 0, 0, limit&&(i==digit[pre]));else if(odd&&i>=last){ans+=dfs(pre-1, i, odd^1, 1, limit&&(i==digit[pre]));}else if(!odd&&i<=last){ans+=dfs(pre-1, i, odd^1, 1, limit&&(i==digit[pre]));}}if(!limit) dp[pre][last][odd]=ans;return ans;
}
int solve(int n){int pre=0;while(n){digit[pre++]=n%10;n/=10;}return dfs(pre-1, 9, 0, 0, 1);//初始状态;根据题意x=a[0]a[1]a[2]......, 开始是偶数位;又1是满足条件的, 所以将第一位的前一位初始化为9;
}
int main(){int T;scanf("%d", &T);memset(dp, -1, sizeof(dp));while(T--){int l, r;cin >>l >> r;cout << solve(r) - solve(l-1) << endl;}return 0;
}
这篇关于Mountain Number FZU - 2109(数位DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!