啊,连了一天的动态规划,快给我整吐了,不过状压DP还没学,效率太低了,明天再用一天学完DP加上图论数据结构,然后拿出两整天的时间来学数论,如果济南夏令营还去的话,回来就备考初赛
数位dp的题,一般会给你l和r,求从l到r有多少个数满足某个性质
我们用f(i)表示前i位windy数的个数
那么答案就是f(r+1)-f(l)有点类似于区间DP
设f[i][j]表示位数位i最高位是j的windy数个数
方程:
f[i][j]=f[i-1][k]其中k是非负整数,k是0,9之间的数
边界f[1][i]=1其中i是非负整数,i是0,9之间的数
怎么求f(x)?
为了方便先对x进行10进制拆分,这个操作很经典
1.显然位数比x小的数字都在1,x区间直接统计
2.位数和x一样最高位数字比x小的数字都在1,x区间直接统计
3.位数和x一样最高位和x一样,从左往右扫一遍x各个位,然后判断合法就好了
#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long ll; const int SIZE=20; ll f[SIZE][SIZE]; ll a[SIZE]; ll n,m; ll sol(ll x) { int len=0; while(x>0ll) a[++len]=x%10,x/=10; ll sum=0ll;//0ll相当于0,长整型下的0 for(int i=1;i<=len-1;i++) for(int j=1;j<=9;j++)//枚举每一位数 sum+=f[i][j];//计算所有可能的数 for(int i=1;i<a[len];i++) sum+=f[len][i]; for(int i=len-1;i>=1;i--) { for(int j=0;j<=a[i]-1;j++) if(abs(j-a[i+1])>=2) sum+=f[i][j]; if(abs(a[i+1]-a[i])<2) break;//小优化 } return sum; } int main() { cin>>n>>m; if(n>m) swap(n,m); for(int i=0;i<=9;i++) f[1][i]=1ll;//初始化1 for(int i=2;i<=10;i++) { for(int j=0;j<=9;j++) { for(int k=0;k<=9;k++) { if(abs(k-j)>=2) f[i][j]+=f[i-1][k];//计算f } } } cout<<sol(m+1)-sol(n)<<endl; return 0; }