首页 > 代码库 > LightOJ 1205 - Palindromic Numbers (数位dp)
LightOJ 1205 - Palindromic Numbers (数位dp)
LightOJ 1205 - Palindromic Numbers (数位dp)
ACM
题目地址:SPOJ MYQ10 Mirror Number
题意:
求[a,b]中回文的个数。
分析:
是SPOJ MYQ01的简单版...其实有非递归方法的。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: 1205.cpp * Create Date: 2014-08-02 16:21:04 * Descripton: digit dp, palindrome */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 20; int t, len, rec[N], bit[N]; ll a, b, dp[N][N][2]; ll dfs (int start, int cur, bool ismir, bool limit) { if (cur < 0) return ismir; if (!limit && dp[start][cur][ismir] != -1) return dp[start][cur][ismir]; int mmax = limit ? bit[cur] : 9; ll ret = 0; repf (i, 0, mmax) { rec[cur] = i; if (start == cur && i == 0) { // if have lead zero ret += dfs(start - 1, cur - 1, ismir, (limit && (i == mmax))); } else if (ismir && cur < (start + 1) / 2) { // if ismirror and can judge ret += dfs(start, cur - 1, (i == rec[start - cur]), (limit && (i == mmax))); } else { ret += dfs(start, cur - 1, ismir, (limit && (i == mmax))); } } return limit ? ret : dp[start][cur][ismir] = ret; } ll calc(ll n) { len = 0; while (n) { bit[len++] = n % 10; n /= 10; } bit[len] = 0; return dfs(len - 1, len - 1, 1, 1); } bool check() { repf (i, 0, len / 2 - 1) { if (bit[i] != bit[len - 1 - i]) return false; } return true; } int main() { memset(dp, -1, sizeof(dp)); scanf("%d", &t); int cas = 1; while (t--) { scanf("%lld %lld", &a, &b); if (a < b) swap(a, b); printf("Case %d: %lld\n", cas++, calc(a) - calc(b) + check()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。