数位DP呀呀

数位DP呀呀"/>

数位DP呀呀

#include<bits/stdc++.h>
using namespace std;
int f[1005][3];
//lm=1为有限制
int a[1005];
int dfs(int pos,int st,int lm)
{if(pos==0)return st==2;if(f[pos][st]!=-1&&lm==0)return f[pos][st];int x=lm?a[pos]:9;int ans=0;for(int i=0;i<=x;i++){if(st==2||i==4||(st==1&&i==8))ans+=dfs(pos-1,2,lm&&i==x);else if(i==3){ans+=dfs(pos-1,1,lm&&i==x);}else{ans+=dfs(pos-1,0,lm&&i==x);}}if(lm==0)f[pos][st]=ans;return ans;
}
int cal(int x)
{int cnt=0;while(x){a[++cnt]=x%10;x=x/10;}memset(f,-1,sizeof(f));f[0][0]=1;return dfs(cnt,0,1);
}
int main()
{int n,m;while(1){cin>>n>>m;if(n==m&&!n)break;int ans=cal(m);ans-=cal(n-1);cout<<ans<<'\n';}}

从最高位开始往下记忆化搜索，当当前位置和下一位置同时有限制才能进行限制