吉比特编程题第二题(2018数)代码

记忆化搜索:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int dp[12][5];
int digit[12];
const int a2018[4] = {2, 0, 1, 8};
int dfs(int pos, int i, bool limit) {
    if(pos==-1) {
        return i == 4;
    }
    if(!limit && dp[pos][i]!=-1) {
        return dp[pos][i];
    }
    int ans = 0;
    int up = limit? digit[pos] : 9;
    for(int j = 0; j <= up; ++ j) {
        if(j == a2018[i]) {
            ans += dfs(pos-1, i+1, limit&(j==up));
        }
        else {
            ans += dfs(pos-1, i, limit&j==up);
        }
    }
    if(!limit) {
        dp[pos][i] = ans;
    }
    return ans;
}
int f(int n) {
    int len = -1;
    while(n) {
        digit[++len] = n%10;
        n /= 10;
    }
    return dfs(len, 0, true);
}
int main() {
    int n;
    while(~scanf("%d", &n)) {
        memset(dp, -1, sizeof(dp));
        printf("%d\n", f(n));
    }
    return 0;
}

update:这题是数位dp问题,上面的代码用的时记忆化搜索,思路就是把小于等于n的数都搜一遍,但是有很多结果是重复的,所以加个数组把每次计算出的结果都保存下来,比如要找小于55555555的“2018”数,那么以13开头的13xxxxxx和以14开头的14xxxxxx的“2018”数的个数是一样的;大家可以网上找找数位dp的入门帖子学学。

#吉比特#
全部评论
import java.util.Scanner; /**  * Created by jia on 2018/9/3.  */ public class Main {     public static void main(String[] args) {             Scanner sc = new Scanner(System.in);             String x   = sc.nextLine();             int num = Integer.valueOf(x);             int count = 0;            if (num < 1000000000){                 while(num >999){                     char [] arr = String.valueOf(num).toCharArray();                     StringBuilder str = new StringBuilder();                     for(int i = 0; i < arr.length;i++ ){                         if(arr[i] == '2'){                             str.append("2");                         }                         if(arr[i] == '0'){                             str.append("0");                         }                         if(arr[i] == '1'){                             str.append("1") ;                         }                         if(arr[i] =='8' ){                             str.append("8");                         }                     }                     if (str.toString().equals("2018")){                         count++;                     }                     num --;                 }             }         System.out.print(count);     } }
点赞 回复
分享
发布于 2018-09-10 00:23
大佬啊,很强
点赞 回复
分享
发布于 2018-09-03 20:58
秋招专场
校招火热招聘中
官网直投
有题目么
点赞 回复
分享
发布于 2018-09-03 21:01
大佬!
点赞 回复
分享
发布于 2018-09-03 21:02
大佬,可以提供个思路吗?直接代码不懂啊
点赞 回复
分享
发布于 2018-09-03 21:05
大佬强
点赞 回复
分享
发布于 2018-09-03 21:06
大佬能稍微解释一下吗,看不懂啊
点赞 回复
分享
发布于 2018-09-03 21:08
小于等于 是怎么做到的
点赞 回复
分享
发布于 2018-09-03 21:17
题目来了
点赞 回复
分享
发布于 2018-09-03 21:42
大佬,选择题160个箱子,轮流取1-5,a第一个取多少可以保证一定可以取到160,这道题怎么解,谢谢大佬
点赞 回复
分享
发布于 2018-09-04 08:13
 public static void method_1_1(int n){   int []stack={2, 0, 1, 8};   int index=0;   //统计2018数的个数   int count=0;   //遍历   for(int i=2018; i<=n; i++){    String s=i+"";    //遍历这个数    for(int j=0; j<s.length(); j++){     if((s.charAt(j)-'0')==stack[index]){      index++;      //如果找到了2018数      if(index==4){       count++;       break;      }     }    }    index=0;   }   System.out.println(count);    }
点赞 回复
分享
发布于 2018-09-05 16:35
我这种菜鸡做法对不,测试数据是多少
点赞 回复
分享
发布于 2018-09-10 00:25
结果不对啊根本
点赞 回复
分享
发布于 2019-04-10 21:26

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务