数位dp模板
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3555
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int dat[20];
ll dp[20][2];
ll DFS(int len, bool lead, bool limit) {
if (len < 0)return 1;
if (!limit&&dp[len][lead])return dp[len][lead];
ll sum = 0, up = limit ? dat[len] : 9;
for (int i = 0; i <= up; i++) {
if (lead&&i == 9)continue;
sum += DFS(len-1,i==4,limit&&i==up);
}
if (!limit)dp[len][lead] = sum;
return sum;
}
ll solve(ll num) {
int cnt = 0;
while (num) {
dat[cnt] = num % 10;
num /= 10;
cnt++;
}
return DFS(cnt-1,false,true);
}
int main() {
ios::sync_with_stdio(false);
int t; cin >> t;
memset(dp,0,sizeof(dp));
while (t--) {
ll n; cin >> n;
cout << n + 1 - solve(n) << endl;
}
return 0;
}
题目二:http://acm.hdu.edu.cn/showproblem.php?pid=2089
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int dat[20];
int dp[20][2];
int DFS(int len, bool lead, bool limit) {
if (len < 0)return 1;
if (!limit&&dp[len][lead])return dp[len][lead];
int sum = 0, up = limit ? dat[len] : 9;
for (int i = 0; i <= up; i++) {
if (lead&&i == 2)continue;
if (i == 4)continue;
sum += DFS(len-1,i==6,limit&&i==up);
}
if (!limit)dp[len][lead] = sum;
return sum;
}
int solve(int num) {
int cnt = 0;
while (num) {
dat[cnt] = num % 10;
num /= 10;
cnt++;
}
return DFS(cnt-1,false,true);
}
int main() {
memset(dp,0,sizeof(dp));
int n, m;
while (scanf("%d%d",&n,&m)==2&&n+m) {
cout << solve(m)-solve(n-1) << endl;
}
return 0;
}