HDU 2089 不要62(数位dp)

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2089

       数位dp模板....


AC代码:

#include <bits/stdc++.h>
using namespace std;
int a[10];
int dp[10][10];

int dfs(int pos, int pre, bool limit){
  if(pos == -1) return 1;
  if(!limit && dp[pos][pre] != -1) return dp[pos][pre];
  int up = limit ? a[pos] : 9;
  int ans = 0;
  for(int i=0;i<=up;i++){
    if(pre == 6 && i == 2) continue;
    if(i == 4) continue;
    ans += dfs(pos - 1, i, limit && i == a[pos]);
  }
  return limit ? ans : dp[pos][pre] = ans;
}

int solve(int x){
  int pos = 0;
  while(x){
    a[pos++] = x % 10;
    x /= 10;
  }
  return dfs(pos - 1, 0, true);
}

int main()
{
  int l, r;
  while(~scanf("%d%d",&l, &r)){
    if(l == 0 && r == 0) break;
    memset(dp,-1,sizeof(dp));
    printf("%d\n", solve(r) - solve(l - 1));
  }
  return 0;
}

 

全部评论

相关推荐

06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务