问题描述
Sparrow是一只土拨鼠。
作为一只可爱又机智的土拨鼠，Sparrow常常被土拨鼠猎人们盯上。众所周知，土拨鼠很擅长打洞，他把每个洞按照1,2,3,4,……的顺序从小到大编号。为了迷惑土拨鼠猎人，Sparrow只选择了一些编号特殊的洞作为居住地。这些特殊的洞的编号满足以下几个条件：
1.不含前导零。
2.如果位数大于等于三位，则不存在连续三位数字构成“233”。如“15233”，“23345”就不是特殊编号的洞。
3.如果位数大于等于三位，则不能同时满足存在“连续两位数字相等”和“某一个数字恰好等于它右边的数字加一”。如“13396”和“25481”满足条件，而“65377”则不行。
4.特别地，1~99不足三位，它们也是特殊的编号。
现在，天才土拨鼠猎人MLX得到可靠情报，Sparrow藏在编号第N小的特殊的洞里。你能告诉MLX这个洞的编号吗？
解：
记忆化搜索好啊！
定义f[i][j][pr][r1][r2][bj][d] 表示第i+1位填j i+2位为pr r1表示是否有相同 r2 表示是否有递减 d表示是否有前导0
关键是是否有前导0 这个需要特判！
采用记忆化搜索解数位DP 更好更快
code：
//
#include<bits/stdc++.h>
#define ll long long
#define maxnn 40
ll f[maxnn][20][20][2][2];
using namespace std;
ll n;
vector<ll > num;
ll dfs(int i,int j,int pr,int r1,int r2,int bj,int d) {
if(i<=-1) return 1;
ll ans=0;
if((~f[i][j][pr][r1][r2])&&(!bj)) return f[i][j][pr][r1][r2];
int minn;
minn=(bj?num[i]:9);
if(r1==1&&r2==1) {
return 0;
}
int fla=0;
for(int k=0; k<=minn; k++) {
if(d&&k!=0) fla=0;
else
{
if(d&&(k==0)) fla=1;
else
{
if((!d)) fla=0;
}
}
if(k==3&&pr==2&&j==3) {
continue;
}
if(j==k+1&&(!d)) {
if(r2==1) {
continue;
} else {
ans+=dfs(i-1,k,j,1,0,(k==minn)&bj,fla);
continue;
}
} else if(j==k&&(!d)) {
if(r1==1) {
continue;
} else {
ans+=dfs(i-1,k,j,0,1,(k==minn)&bj,fla);
continue;
}
}
else
ans+=dfs(i-1,k,j,r1,r2,(k==minn)&bj,fla);
}
if(!bj) f[i][j][pr][r1][r2]=ans;
return ans;
}
ll isok(ll t) {
memset(f,-1,sizeof(f));
num.clear();
while(t) {
num.push_back(t%10);
t/=10;
}
return dfs(num.size()-1,-2,-2,0,0,1,1)-1;
}
int main() {
//freopen("tes","r",stdin);
//freopen("myp.out","w",stdout);
cin>>n;
ll l=0,r=1e18;
while(l<=r) {
ll mid=(l+r)>>1;
if(isok(mid)>=n) {
r=mid-1;
} else {
l=mid+1;
}
}
cout<<l;
}