ZOJ 3816 Generalized Palindromic Number （数位DP+二分）

ZOJ3816 这题方法很多，暴力的做法我还没看懂，只会用数位DP搞。二分区间，然后数位DP求个数就可以了。

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 <= 1018).

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

#include <stdio.h>

#include

#include <string.h>

#include

#include <math.h>
using namespace std;
long long dp[20][20][20];
int bit[30];
int num[30];
long long dfs(int pos,int now,int aim,bool limit){
if(pos < 0)return now == aim;
if(!limit && dp[pos][now][aim] != -1)
return dp[pos][now][aim];
int end = limit ? bit[pos] : 9;
long long ans = 0;
for(int i = 0;i <= end;i++){
if(now == 0){
if(i == 0){
ans += dfs(pos-1,now,aim,limit && (i == end));
}
else {
num[now] = i;
if(now < aim)ans += dfs(pos-1,now+1,aim,limit && (i == end));
}
}
else {
if(i == num[now-1])ans += dfs(pos-1,now,aim,limit && (i == end));
else {
num[now] = i;
if(now < (aim+1)/2){
if(now < aim)ans += dfs(pos-1,now+1,aim,limit && (i == end));
}
else {
if(i != num[aim-1-now])continue;
if(now < aim)ans += dfs(pos-1,now+1,aim,limit && (i == end));
}
}
}
}
if(!limit)dp[pos][now][aim] = ans;
return ans;
}
long long calc(long long n){
int pos = 0;
do{
bit[pos++] = n%10;
n /= 10;
}while(n);
long long ans = 0;
for(int i = 1;i <= pos;i++)
ans += dfs(pos-1,0,i,1);
return ans;
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
scanf(“%d”,&T);
long long n;
memset(dp,-1,sizeof(dp));
while(T–){
scanf(“%lld”,&n);
n–;
long long tmp = calc(n);
long long l = 0, r = n;
long long ans = 0;
while(l <= r){
long long mid = (l+r)/2;
if(calc(mid) >= tmp){
ans = mid;
r = mid-1;
}
else l = mid+1;
}
printf(“%lld\n”,ans);
}
return 0;
}