一个奇怪的东西
正反都能dp!: 正常我们数位dp都是从高到低，以这样的方式保证其小于给定数->
ll n; int num[N],l; ll dp[]; ll dfs(int p,int lim){ if(p==0) return 1; if(!lim&&~dp[]) return dp[]; int Uplim=lim?num[p]:9; ll res=0; for(int i=0;i<=Uplim;i++) { res+=dfs(p-1,lim&&(i==Uplim)); } if(!lim) dp[]=res; return res; } int main(){ scanf("%lld",&n); while(n) num[++l]=n,n/=10; printf("%lld\n",dfs(l,1)); }然而从低到高位应该是这样的:
ll n; int num[N],l; ll dp[]; ll dfs(int p,int fl){ if(p==l+1) return fl; if(~dp[]) return dp[]; ll res=0; for(int i=0;i<10;i++) { res+=dfs(p+1,i<num[p]||(i==num[p]&&fl)); } return dp[]=res; } int main(){ scanf("%lld",&n); while(n) num[++l]=n,n/=10; printf("%lld\n",dfs(1,1)); }这个在某些特殊情况下可以消除一些后效性和麻烦的步骤
注意每次跑不同数的时候要清空dp
转载于:https://www.cnblogs.com/chasedeath/p/11269342.html
