首页 > 代码库 > BZOJ1026 SCOI2009 Windy数 一般DP

BZOJ1026 SCOI2009 Windy数 一般DP

2024-09-06 01:21:35   218人阅读

题意：求[A,B]之间，任意相邻两位差值均大于等于2的数的个数题解：设f[i][j]=第i位为j的合法的数的数量，显然有f[i][j]=f[i-1][k],|k-j|≥2。至于统计答案，我们只要能求1-U之间的合法的数的数量，显然答案就是Ans[B]-Ans[A-1]。至于Ans[i]……因为Ans[10^t]比较好求，所以一位一位统计就好。

技术分享
#include <cmath>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXN=10;ll A,B,f[MAXN+2][MAXN+2];ll Calc(ll x){    int N=0,g[MAXN];    ll Ans=0;    if(!x) return 0;    memset(g,0,sizeof(g));    while(x) g[++N]=x%10,x/=10;    for(int i=1;i<g[N];i++) Ans+=f[N][i];    for(int i=N-1;i;i--)        for(int j=1;j<=9;j++) Ans+=f[i][j];    for(int i=N-1;i;i--){        for(int j=0;j<g[i];j++)            if(abs(g[i+1]-j)>=2) Ans+=f[i][j];        if(abs(g[i+1]-g[i])<2) break;    }    return Ans;}int main(){    cin >> A >> B;    for(int i=0;i<=9;i++) f[1][i]=1;    for(int i=2;i<=MAXN;i++)        for(int j=0;j<=9;j++)            for(int k=0;k<=9;k++)                if(abs(j-k)>=2) f[i][j]+=f[i-1][k];    cout << Calc(B+1)-Calc(A) << endl;    return 0;}
View Code

 

BZOJ1026 SCOI2009 Windy数 一般DP


联系
我们