[bzoj1026][SCOI2009]windy数_数位dp

2021-02-09 15:17

阅读：687

windy数 bzoj-1026

　　　　题目大意：求一段区间中的windy数个数。

　　　　注释：如果一个数任意相邻两位的差的绝对值都不小于2，这个数就是windy数，没有前导0。$区间边界

　　　　　　想法：数位dp裸题，何为数位dp?

　　　　　　数位dp的意思就是我们交换一种dp的方式。通过数位进行dp。数位dp的主旨分为两点：1.对于所求答案的预处理。2.对于所求区间的边界特判。我们对于数位dp有几个显而易见但是却比较useful的性质：

　　　　　　　　如果一个数的位数小于第二个数的位数，那么后者是大于前者的。

　　　　　　　　如果两个数的位数相等且前者的最高位是小于后者的最高位的，那么后者是大于前者的。

　　　　　　　　如果将两个数同时加减同一个数，他们之间的大小关系显然是不变的。

　　　　　　通过以上几个性质，我们在枚举边界时可以先将位数小的全部枚举，然后对于高位到低位依次dp。

　　　　　　回到这道题，我们先设状态dp[i][j]表示i位数且最高位为j。在转移时，我们其实很容易想到

　　　　　　　　$\sum\limits_{k=0}^{9}dp(i-1,k)\cdot [|j-k|\ge 2]$

　　　　　　之后，关于边界的处理，看代码... ...

　　　　最后，附上丑陋的代码... ...

#include 
#include 
#include 
#include 
typedef long long ll;
using namespace std;
int f[20][20];
void before_hand()//这个是预处理，在上面说的很清楚了
{
	memset(f,0,sizeof f);
	for(int i=0;i=2) f[i][j]+=f[i-1][k];
	}
}
int dig[20];
ll dispose(ll x)//对边界的处理
{
	int ans=0;
	int k=0;
	memset(dig,0,sizeof dig);
	if(!x) return 0;
	while(x)
	{
		dig[++k]=x%10;
		x/=10;
	}
	for(int i=1;i=1;i--)//反复运用第二、三个性质
	{
		for(int j=0;j=2) ans+=f[i][j];
		}
		if(abs(dig[i+1]-dig[i])

　　　　小结：前面预处理的边界不要忘记特判。数位dp的第一道题，加油，JZYshuraK

上一篇：windows安装linux虚拟机、修改apt源

下一篇：windows中使用Git如何解决文件冲突？

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[bzoj1026][SCOI2009]windy数_数位dp
文章链接：http://soscw.com/essay/53146.html

亲，登录后才可以留言！

[bzoj1026][SCOI2009]windy数_数位dp

评论

热门文章

推荐文章

最新文章

置顶文章