首页 > 代码库 > uestc250windy数数位dp
uestc250windy数数位dp
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int dp[100][100][2];int up[1000];int ab(int x){ return x>0? x:-x;}int dfs(int pos,int top,int first,int flag){ if(pos<=0) return first==1; if(first&&!flag&&~dp[pos][top][first]) return dp[pos][top][first]; int limit = flag? up[pos]: 9,ret=0; for(int i= 0;i<=limit;i++){ int t= ab(top-i); if(t>=2||!first) ret+=dfs(pos-1,i,first||i,flag&&(i==limit)); //这个判断是海哥告诉的,非常吊,自己品味。 } return flag? ret: dp[pos][top][first] = ret;}int solve(int x){ int len=0; while(x){ up[++len]=x%10; x/=10; } return dfs(len,100,0,1);}int main(){ memset(dp,-1,sizeof(dp)); int n,m; while(scanf("%d%d",&n,&m)!=EOF){ cout<<solve(m) - solve(n-1) <<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。