Windy数
2021-07-08 16:06
阅读：791
标签：部分 昨天 比较 模板 [1] scanf int http 过程
昨天看了数位dp，虽然还是有点没懂不过水一发板子题先
题目链接：[SCOI2009]windy数
这道题大概是数位dp的模板了，状态转移方程也比较显然。
设f[i][j]表示i位数，首位是j的windy数的数量，则容易有状态转移方程：
f[i][j]=sum(f[i-1][k])(abs(j-k)>=2)然后我们用这样几个循环先把这个f数组预处理一下（即在数据范围内的所有的windy数的数量）
for(int i=2;i=2)f[i][j]+=f[i-1][k];计算区间[A,B]内的windy数，可以考虑前缀和，求出[0,B]内的windy数和[0,A-1]内的windy数，然后相减输出。
对于求[0,B]区间内的windy数，设B有k位，考虑分为三段：
- 求出k-1位长的windy数
- 求出“k位长，首位小于B的最高位”的windy数
-
求出k位长，首位为B的最高位的windy数
这样就可以囊括完所有的部分
对于第三步，我们可以通过一个这样的过程来求解：
首先统计长度为k-1,最高位为i(0
代码如下：
#include
using namespace std;
long long x,y;
long long f[15][15];
long long digit[15];
void dp(){
memset(f,0,sizeof(f));
for(int i=0;i=2)
for(int j=0;j=2)f[i][j]+=f[i-1][k];
}
long long solve(long long x){
memset(digit,0,sizeof(digit));
long long cnt=0,ans=0;
if(x==0)return 0;
while(x){
digit[++cnt]=x%10;
x/=10;
}
for(int i=1;i=1;i--){
for(int j=0;j=2)ans+=f[i][j];
if(abs(digit[i]-digit[i+1]) Windy数
标签：部分 昨天 比较 模板 [1] scanf int http 过程
原文地址：https://www.cnblogs.com/kma093/p/9736158.html
评论
亲，登录后才可以留言！