【一本通提高数位动态规划】windy数
标签：https sizeof res lin 数位dp onclick ble get 规划
传送门【一本通提高数位动态规划】windy数
#includeusing namespace std;
#define ll long long
ll dp[15][15],ans;
bool vis[15][15];
ll a[15];
ll l,r,len;
ll dfs(ll pos,ll pre,ll zero,ll limit)
{
if(pos>len)return 1;
if(!limit&&vis[pos][pre])return dp[pos][pre];
ll res=limit?a[len-pos+1]:9,ret=0;
for(int i=0;i)
{
if(abs(i-pre)2) continue;
if(zero&&i==0) ret+=dfs(pos+1,-2,1,limit&&i==res);
else ret+=dfs(pos+1,i,0,limit&&i==res);
}
if((!limit)&&(!zero))dp[pos][pre]=ret;
vis[pos][pre]=1;
return ret;
}
inline void get(ll x)
{
len=0;
while(x)a[++len]=x%10,x/=10;
}
int main()
{
scanf("%lld%lld",&l,&r);
get(r);
ll ans=dfs(1,-2,1,1);
memset(dp,0,sizeof dp);
memset(vis,0,sizeof vis);
get(l-1);
ll ans1=dfs(1,-2,1,1);
printf("%lld",ans-ans1);
}
数位DP
数位DP详解
【一本通提高数位动态规划】windy数
标签：https sizeof res lin 数位dp onclick ble get 规划
原文地址：https://www.cnblogs.com/yanghaokun/p/10605720.html
评论