https://www.luogu.org/problemnew/show/P2657

不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。

这道题是个显然到不能再显然的数位dp了。

来个最神奇的dp[i][j]表示i位数,开头为j的windy数的个数吧。

那么dp[i][j]的求法是很显然的,写个sum数组求和更为方便。

那么怎么统计windy数呢?

约定由布丁酱写的数位dp,求闭区间[l,r]时,使用count(r)-count(l-1),也就是count(x)表示不小于的[0,x]中windy数的个数。

怎么求count呢,最简单的思路就是分类讨论。

对最高位分三类:

  最高位为0,遍历所有的dp[i][1~9]再加上0本身。

  最高位为非0且比x最高位小,后面满足条件的可以随意取。

  最高位相等,交给下一位去做。

对非最高位分两类:

  该位在受前面位的限制下任取,后面满足条件的任取。

  该位相等,交给下一位去做。(小心该位相等时非法,找了很久!

最后补上x本身的判断。

最后要小心爆int……

意思是说,在数位dp的时候,每一步分类要不重不漏,每一步要判断合法。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[][]; ll sum(int i,int j1,int j2){
/*if(i==0)
return 1;*/
if(j1<)
j1=;
if(j2>)
j2=;
ll res=;
for(int j=j1;j<=j2;j++){
res+=dp[i][j];
}
return res;
} void init(){
for(int j=;j<=;j++)
dp[][j]=;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
dp[i][j]=sum(i-,,j-)+sum(i-,j+,);
}
} /*for(int j=1;j<=2;j++){
dp[9][j]=sum(8,0,j-2)+sum(8,j+2,9);
}*/ /*for(int i=1;i<=9;i++){
for(int j=0;j<=9;j++){
printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);
}
printf("\n");
}*/
} ll A,B;
int digit[]; ll count(ll x){
//cout<<"x="<<x<<endl;
if(x==)
return ;
//否则岂不是0位数?
ll k=,cx=x;
digit[k++]=;
//占位用的
while(cx){
digit[k++]=cx%;
cx/=;
}
k--;
digit[k+]=;
//也是占位 ll res=;
for(int i=k;i>=;i--){
//printf("res=%d\n",res);
if(i==k){
//最高位取0
for(int ii=i-;ii>=;ii--)
res+=sum(ii,,);
res+=;//0
//其实不用特判啊
for(int j=;j<digit[i];j++){
//最高位比digit小且不为0
if(i->=){
res+=sum(i-,,j-)+sum(i-,j+,);
}
else{
res+=;
}
}
//最高位就取相等,问题留给下一次循环
}
else{
//前面的位都相等,非最高位的情况,双重受限
for(int j=;j<digit[i];j++){
if(abs(digit[i+]-j)<=)
;//被前一位限制取值
else if(i->=){
res+=sum(i-,,j-)+sum(i-,j+,);
}
else{
res+=;
}
}
}
} for(int i=;i<=k;i++){
if(abs(digit[i]-digit[i-])<=){
//printf("res1=%d\n",res);
return res;
}
}
//printf("res2=%d\n",res+1);
return res+;
} int main(){
init();
while(~scanf("%lld%lld",&A,&B)){
printf("%lld\n",count(B)-count(A-));
}
}

后来学会了另一种写法。搜索写法这种写法里要用到lead来指定new_state1的状态。

#include<bits/stdc++.h>
using namespace std;
#define ll long long int a[];
ll dp[][/*前一位的取值,只有0~9*/];//不同题目状态不同
ll dfs(int pos,int state1/*前一位的取值,只有0~9,-1表示不受限制*/,bool lead/*这一位的前面是否为零*/,bool limit/*这一位是否取值被限制(也就是上一位没有解除限制)*/)
//不是每个题都要处理前导零
{
//递归边界,最低位是0,那么pos==-1说明这个数枚举完了
if(pos==-)
return ;/*这里返回1,表示枚举的这个数是合法的,那么这里就需要在枚举时必须每一位都要满足题目条件,也就是说当前枚举到pos位,一定要保证前面已经枚举的数位是合法的。 */
//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
if(!limit && !lead && dp[pos][state1]!=-)
return dp[pos][state1];
/*常规写法都是在没有限制的条件记忆化,这里与下面记录状态对应*/
int up=limit?a[pos]:;//根据limit判断枚举的上界up
ll ans=;
//开始计数
for(int i=; i<=up; i++) { //枚举,然后把不同情况的个数加到ans就可以了
int new_state1=i;
if(lead==true&&i==){
//这一位继续是前导0,new_state1应为-1
new_state1=-;
}
if(state1>=&&abs(new_state1-state1)<)
continue;
/*
计数的时候用continue跳过不合法的状态,不再搜索
*/ //合法的状态向下搜索
ans+=dfs(pos-,new_state1,lead && i==,limit && i==a[pos]);//最后两个变量传参都是这样写的
}
//计算完,记录状态
if(!limit && !lead)
dp[pos][state1]=ans;
/*这里对应上面的记忆化,在一定条件下时记录,保证一致性,当然如果约束条件不需要考虑lead,这里就是lead就完全不用考虑了*/
return ans;
} ll solve(ll x) {
//可能需要特殊处理0或者-1
if(x<=)
return ; int pos=;
while(x) { //把数位分解
a[pos++]=x%;//编号为[0,pos),注意数位边界
x/=;
} return dfs(pos-/*从最高位开始枚举*/,-/*表示这一位前面并没有对其限制的高位*/,true,true);//刚开始最高位都是有限制并且有前导零的,显然比最高位还要高的一位视为0嘛
} int main() {
memset(dp,-,sizeof(dp));
//一定要初始化为-1 ll le,ri;
while(~scanf("%lld%lld",&le,&ri)) {
printf("%lld\n",solve(ri)-solve(le-));
}
}

最新文章

  1. 在windows下面配置redis集群遇到的一些坑
  2. 在Javascript中监听flash事件(转)
  3. JSON value
  4. CSS Counters 计数属性
  5. printf函数重定向
  6. C++访问权限
  7. 夏梦竹谈Hive vs. HBase的区别
  8. Openlayers 3 热力图
  9. 关于IP网段间互访的问题—路由是根本(转)
  10. Java并发编程:线程的基本状态
  11. MacBook 经常使用快捷键
  12. Coding语言强弱类型且动静态类型简单解析。附图解
  13. JavaSE assert断言的学习
  14. 百度分享不支持Https的解决方案--本地化
  15. malloc()參数为0的情况
  16. 解决linux系统CentOS下调整home和根分区大小
  17. 用java打暴雪星际争霸(2)——执行測试机器人
  18. CSV 中添加逗号
  19. NOIP 算法模板
  20. git 提交代码出现git Permission to Xx denied to Xx 错误

热门文章

  1. 有方向的运动js
  2. PostgreSQL触发器的使用
  3. vim编码方式配置的学习和思考
  4. no matching provisioning profiles found
  5. 加载和执行 --《高性能JavaScript》
  6. 深入理解Atomic原子操作和volatile非原子性
  7. 关于Cascading
  8. archlinux yaourt安装 以及出错细节 database file for &quot;archlinuxfr&quot; does not exist.
  9. Cocos2d-js异步图片加载
  10. amazon lightsail