首页 > 代码库 > ZOJ - 3816 Generalized Palindromic Number dfs
ZOJ - 3816 Generalized Palindromic Number dfs
A number that will be the same when it is written forwards or backwards is known as a palindromic number. For example, 1234321 is a palindromic number.
We call a number generalized palindromic number, if after merging all the consecutive same digits, the resulting number is a palindromic number. For example, 122111 is a generalized palindromic number. Because after merging, 122111 turns into 121 which is a palindromic number.
Now you are given a positive integer N, please find the largest generalized palindromic number less than N.
Input
There are multiple test cases. The first line of input contains an integer T (about 5000) indicating the number of test cases. For each test case:
There is only one integer N (1 <= N <= 1018).
Output
For each test case, output the largest generalized palindromic number less than N.
Sample Input
41212312241122
Sample Output
1112112211121
Author: LIN, Xi Source: The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
转自：http://blog.csdn.net/u011345136/article/details/39122741
题意：求小于N的回文数，这个数的回文相同的数可以缩成一个数
思路：dfs(l, r, flag)：l代表左边侧长度，r代表右边的长度，flag代表是否处于边界，然后在搜索右边匹配左边的同时，枚举k，k代表右边连续相同的数都匹配左边的个数
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 10 #define N 55 11 #define M 15 12 #define mod 6 13 #define mod2 100000000 14 #define ll long long 15 #define maxi(a,b) (a)>(b)? (a) : (b) 16 #define mini(a,b) (a)<(b)? (a) : (b) 17 18 using namespace std; 19 20 int T; 21 ll n; 22 char s[N]; 23 ll ans; 24 int len; 25 char leftnum[N]; 26 char rightnum[N]; 27 28 void ini() 29 { 30 // scanf("%lld",&n); 31 cin>>n; 32 ans=-1; 33 //memset(left,0,sizeof(left)); 34 //memset(right,0,sizeof(right)); 35 sprintf(s+1,"%lld",n); 36 //sprintf(s+1,"%I64d",n); 37 len=strlen(s+1); 38 for(int i=1;i<=len;i++){ 39 s[i]-=‘0‘; 40 } 41 } 42 43 void out() 44 { 45 //printf("%lld\n",ans); 46 cout<<ans<<endl; 47 } 48 49 ll getans(int l,int r) 50 { 51 ll re=0; 52 int i; 53 for(i=1;i<=l;i++){ 54 re=re*10+leftnum[i]; 55 } 56 for(i=r;i>=1;i--){ 57 re=re*10+rightnum[i]; 58 } 59 return re; 60 } 61 62 ll dfs(int l,int r,int flag) 63 { 64 ll re=-1; 65 int i,k,m; 66 if(l+r-1>len) return -1ll; 67 if(l+r-1==len){ 68 re=getans(l-1,r); 69 if(re>=n) return -1ll; 70 return re; 71 } 72 73 m= (flag==1) ? s[l] : 9; 74 for(i=m;i>=0;i--) 75 { 76 leftnum[l]=i; 77 if( (l==1 || leftnum[l]!=leftnum[l-1]) && !(l==1 && i==0) && (l+r!=len) ) 78 { 79 for(k=1;k+l+r<=len;k++){ 80 rightnum[k+r]=i; 81 re=max(re,dfs(l+1,r+k,flag && (m==i) ) ); 82 } 83 } 84 else{ 85 re=max(re,dfs(l+1,r,flag && (m==i) )); 86 } 87 if(re>0){ 88 return re; 89 } 90 } 91 return re; 92 } 93 94 int main() 95 { 96 //freopen("data.in","r",stdin); 97 scanf("%d",&T); 98 for(int cnt=1;cnt<=T;cnt++) 99 // while(T--)100 //while(scanf("%I64d%I64d%I64d",&a,&b,&c)!=EOF)101 {102 ini();103 ans=dfs(1,0,1);104 out();105 }106 107 return 0;108 }
ZOJ - 3816 Generalized Palindromic Number dfs