题解 P2657 【[SCOI2009] windy 数】 -- 数位dp
jijidawang
2020-05-18 22:06:18
数位 dp。
```cpp
// 数位 dp 其实是爆搜加记忆化
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=15; //数据范围是 10^n 就可以开 n 那么大的数组。
int dp[N][2][2][N],a[N]; //dp 数组用来记忆化，a 数组用来数位分离
int dfs(int loc,bool limit,bool lead,int pre)
// loc : 目前搜到的位数
// limit : 前一位是否为最大值，比如 123 中百位搜到了 1（最大），那么十位如果搜到了 1 那么各位就可以搜 0~9，如果十位搜到了 2 那么个位就只能搜 0~3 了。
// lead : 是否有前导零，如果有前导零就不用处理相邻两位 abs >=2 的条件了（因为前导零不计入计算）。
// pre : 搜到的上一位的数字，用于判断相邻两位 abs >=2。
{
if (!loc) return 1; //如果搜到了最后一位果断返回 1
if (dp[loc][limit][lead][pre]!=-1) return dp[loc][limit][lead][pre]; //如果搜过了果断返回
int ans=0,maxbit=limit?a[loc]:9; //maxbit 代表能搜的数位 0~maxbit，ans 累加答案。
for (int i=0;i<=maxbit;i++) //枚举这一位的所有可能性，记得有等号
if (lead||abs(pre-i)>=2) ans+=dfs(loc-1,limit&(i==a[loc]),lead&(i==0),i);
// 如果有前导零或者满足相邻两位 abs >=2，那么搜索。
// 下一位的 loc 显然是目前的 loc-1；
// 下一位的 limit 在这一位搜到了极限（即 limit=1）的且 i==a[loc]（目前的这一位最大）的条件下才可以，需要用 &。
// 下一位的 lead 在这一位有前导零的条件下（如果不判断那么 303 也会被判做有前导零了）且这一位为零的条件下才可以，同 limit，需要用 &。
// pre 显然是 i。
return dp[loc][limit][lead][pre]=ans; //记忆化
}
int solve(int q) // 1~q 的数字数量
{
memset(dp,-1,sizeof dp); //将 -1 视作为搜到的状态表示
int len=0; //数字位数
while (q){a[++len]=q%10;q/=10;} //数位分离
return dfs(len,1,1,0);
// 首先 loc 肯定是 len，从高往低搜嘛
// limit 肯定是 1，相当于我们在每个数字前面加上一个前导零，这样最高位就不会溢出（？）了。
// lead 同 limit，建立一个前导零。
// pre 同 lead,limit 建立了前导零，所以 pre 肯定是 0 了。
}
int main()
{
int l,r;
cin>>l>>r;
cout<<solve(r)-solve(l-1); //用前缀和思想相减。
return 0;
}
```