数位dp总结 之 从入门到模板 |
您所在的位置：网站首页 › 数位产品和数字是一样吗 › 数位dp总结 之 从入门到模板 |
|
基础篇 数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！ 之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。 两种不同的枚举：对于一个求区间[le,ri]满足条件数的个数，最简单的暴力如下： for(int i=le;i0) return 0;//最坏的情况，这一位及后面的全部为9都不能达到0那就直接GG，这个剪枝不会影响ac if(pos==-1) return sum==0 && val==0; if(dp[pos][sum][val][limit]!=-1) return dp[pos][sum][val][limit]; int up=limit?a[pos]:9; ll ans=0; for(int i=0;i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |