吉比特编程题第二题(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的入门帖子学学。
#吉比特#
投递美团等公司10个岗位 >
