Generalized Palindromic Number

---

Time Limit: 2 Seconds      Memory Limit: 65536 KB

---

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 <= 10¹⁸).

Output

For each test case, output the largest generalized palindromic number less than N.

Sample Input

4

12

123

1224

1122

Sample Output

11

121

1221

1121

---

Author: LIN, Xi

Source: The 2014 ACM-ICPC Asia Mudanjiang Regional First Round

解题思路：

题意为给定一个数n。求小于n的最大“回文数”， “回文数”要求连续同样的数能够压缩成一个数，比方1233221，能够压缩成12321，是回文数。

思路为暴力枚举，相当于填数字。首先枚举填左边第一个数字从大到小。然后在里面枚举右边有多少个和它一样的数，注意剪枝，左边当前数字假设符合题意的话，就不用再继续枚举当前数字了。由于要求最大。详细思路在代码凝视中。

參考：http://blog.csdn.net/u011345136/article/details/39122741

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

using namespace std;

#define ll long long

const int maxn=20;

int Left[maxn],Right[maxn];//回文数左部分和右部分，比方 1511 ，左边存1 5 右边存 1 1

string str;//输入字符串

int len;//长度

ll n;//字符串代表的数字

ll lmax(ll a ,ll b)

{

    return a>b?a:b;

}

ll getNum(int l,int r)//获得当前回文数的值

{

    ll ans=0;

    for(int i=1;i<=l;i++)

        ans=ans*10+Left[i];

    for(int i=r;i>=1;i--)//注意存储的顺序，原数的最后一位是Left数组存储的第一位

        ans=ans*10+Right[i];

    return ans;

}

ll dfs(int l,int r,int cur)//左边数字的个数l，右边数字的个数r，当前数字是否是边界。比方2511,第一位2就是边界，回文数该位要<=2。其它位就不是边界，能够从9開始

{

    ll ans=-1;

    if(l+r-1==len)//由于dfs參数中的l。dfs中给左边第l位赋值。而递归參数为l+1，所以当(l-1+r)=len时才是递归出口

    {

        ans=getNum(l-1,r);

        if(ans>=n) return -1;//别忘了，不能大于等于给定的数 T T

        return ans;

    }

    int now=cur?

(str[l-1]-'0'):9;//给左边第l位赋值。推断是否为边界

    for(int i=now;i>=0;i--)//枚举第l位

    {

        Left[l]=i;

        //假设  当前l是第一位或者不是第一位但当前位和前一位不一样  且  不能l是第一位且i为0  且 数字还没有填完

        if((l==1||(l>1&&Left[l]!=Left[l-1]))&&(!(l==1&&i==0))&&l+r!=len)

        {

            for(int k=1;l+r+k<=len;k++)//枚举右半部分与第l位同样的有多少位

            {

                Right[r+k]=i;

                ans=lmax(ans,dfs(l+1,r+k,cur&&now==i));

            }

        }

        else

        {

            ans=lmax(ans,dfs(l+1,r,cur&&now==i));

        }

        if(ans>0)//假设当前的ans符合题意，就不用再向下搜索了。比方455 第1位4找到一个数符合题意454,那么第一位就不用枚举3 2 1 0了剪枝

            return ans;

    }

    return ans;

}

int main()

{

    int t;cin>>t;

    while(t--)

    {

        cin>>str;

        n=0;

        len=str.length();

        for(int i=0;i<len;i++)

            n=n*10+str[i]-'0';

        ll ans=dfs(1,0,1);

        cout<<ans<<endl;

    }

    return 0;

}