[数位dp+二分] zoj Generalized Palindromic Number

题意：

找一个小于N的最大的且符合题意的数。

题意的数为，通过缩减后是回文的数，所谓的缩减就是相同连续的数看做一个数，如“155451111”其实就是“15451”是符合题意的数。

思路：

通过数位dp，然后二分求解。

dp[i][j][k]代表第i位，已经放了j个数，最后长度是k的缩减回文数有几个。

然后需要一个ok[]数组代表放的数是什么，如果连续放相同的数就等于没放数。

遍历所有的长度就可以得到结果了。

其实不难发现，，这种回文数一定是奇数位的。

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"#include"string"#define mod 1000000009#define ll long longusing namespace std;ll dp[22][22][22];int ok[22],num[22];ll dfs(int site,int n,int c,int f){if(n>c) return 0;if(site==0) return n==c;if(!f&&dp[site][n][c]!=-1) return dp[site][n][c];ll ans=0;int len=f?num[site]:9;for(int i=0;i<=len;i++){if(n==0){if(i==0) ans+=dfs(site-1,n,c,f&&i==len);else{ok[n+1]=i;ans+=dfs(site-1,n+1,c,f&&i==len);}}else{if(i==ok[n]) ans+=dfs(site-1,n,c,f&&i==len);else{if(n<(c+1)/2){ok[n+1]=i;ans+=dfs(site-1,n+1,c,f&&i==len);}else if(i==ok[c-n]){ok[n+1]=i;ans+=dfs(site-1,n+1,c,f&&i==len);}}}}if(!f) dp[site][n][c]=ans;return ans;}ll solve(ll x){int cnt=0;while(x){num[++cnt]=x%10;x/=10;}ll ans=0;for(int i=1;i<=cnt;i+=2) ans+=dfs(cnt,0,i,1);return ans;}int main(){int t;cin>>t;memset(dp,-1,sizeof(dp));while(t–){ll n;scanf("%lld",&n);n–;ll sum=solve(n);ll l=0,r=n,mid,ans;while(l<=r){mid=(l+r)/2;ll tep=solve(mid);if(tep>=sum){ans=mid;r=mid-1;}else l=mid+1;}printf("%lld\n",ans);}return 0;}

如你想要拥有完美无暇的友谊，可能一辈子找不到朋友