首页 > 代码库 > UESTC windy数位dp
UESTC windy数位dp
题目链接:http://acm.uestc.edu.cn/#/problem/show/250
题目描述:
windy数
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为
windy想知道,在
Input
包含两个整数,
满足
Output
Sample input and output
Sample Input | Sample Output |
---|---|
1 10 | 9 |
Source
Windy
题意:如题所说,题意很明确了;
思路:这是我学习数位dp以来,第一道全自主思考+代码实现的题;
dp[i][j][z]:前i位数,以j结尾,z==1表示有前导为0,z==0表示前导不为0 包含windy数的个数
记忆化搜索~当然打表也行~
#include <iostream> #include <stdio.h> #include <string> #include <string.h> using namespace std; int dp[25][25][3]; int bit[25]; int dfs(int pos,int pre,int flag,int z) { if(pos==0)return 1; if( !flag && dp[pos][pre][z]!=-1)return dp[pos][pre][z]; int end=flag?bit[pos]:9; int ans=0; for(int i=0;i<=end;i++) { if( z==1 || pre-i>=2 || i-pre>=2 ) ans+=dfs(pos-1,i,flag&&(i==end),z&&(i==0)); } if(!flag)dp[pos][pre][z]=ans; return ans; } int cal(int x) { int len=0; memset(bit,0,sizeof(bit)); memset(dp,-1,sizeof(dp)); while(x) { bit[++len]=x%10; x/=10; } return dfs(len,0,1,1); } int main() { int l,r; while(scanf("%d%d",&l,&r)!=EOF) { int s1=cal(r); int s2=cal(l-1); printf("%d\n",s1-s2); } return 0; }
UESTC windy数位dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。