首页 > 代码库 > SPOJ - MYQ10 Mirror Number (数位DP)
SPOJ - MYQ10 Mirror Number (数位DP)
Description
A number is called a Mirror number if on lateral inversion, it gives the same number i.e it looks the same in a mirror. For example 101 is a mirror number while 100 is not.
Given two numbers a and b, find the number of mirror numbers in between them (inclusive of a and b).
Input
First line contains T, number of testcases <= 10^5.
Each testcase is described in a single line containing two numbers a and b.
0 <= a<=b <= 10^44
Output
For each test case print the number of mirror numbers between a and b in a single line.
Example
Input: 3 0 10 10 20 1 4 Output: 3 1 1
题意：求镜像回文的个数在[a,b]区间里
思路：相对较难的数位DP，相对于普通的数位DP ，多了两个参数一个是开始的位置，一个是判断是不是镜像回文，
用一个tmp来储存已经放的数字来判断是不是回文
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 50;
ll dp[maxn][maxn][2];
char num[maxn];
int tmp[maxn];
//cur：当前位数，start：镜像回文判断的开始地方，flag：是否是镜像回文，limit：边界判断
ll dfs(int cur, int start, bool flag, bool limit) {
if (cur == -1)
return flag;
if (!limit && dp[cur][start][flag] != -1)
return dp[cur][start][flag];
ll ans = 0;
int end = limit?(num[cur]-48):9;
for (int i = 0; i <= end; i++) {
if (i == 0 || i == 1 || i == 8) {
bool st = (cur==start && i == 0); //判断是否是0情况
bool newFlag = flag;
if (flag) {
if (!st && cur < (start+1)/2)
newFlag = (tmp[start-cur] == i);
}
tmp[cur] = i;
ans += dfs(cur-1, st?start-1:start, newFlag, limit&&(i==end));
}
}
if (!limit)
dp[cur][start][flag] = ans;
return ans;
}
ll cal(char str[]) {
int len = strlen(str);
for (int i = 0; i < len; i++)
num[i] = str[len-1-i];
num[len] = 0;
return dfs(len-1, len-1, 1, 1);
}
int main() {
int t;
char a[maxn], b[maxn];
scanf("%d", &t);
getchar();
memset(dp, -1, sizeof(dp));
while (t--) {
scanf("%s %s", a, b);
ll ans = cal(b) - cal(a);
int len = strlen(a);
bool flag = true;
for (int i = 0; i < len; i++)
if ((a[i] != '0' && a[i] != '1' && a[i] != '8') || (a[i] != a[len-1-i])) {
flag = false;
break;
}
if (flag)
ans++;
printf("%lld\n", ans);
}
return 0;
}SPOJ - MYQ10 Mirror Number (数位DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。