C++ 洛谷 P2657 [SCOI2009]windy数 题解

P2657 [SCOI2009]windy数

同步数位DP

这题还是很简单的啦（差点没做出来

个位打表大佬请离开（包括记搜），我这里讲的是DP!!!

首先Cal(b+1)-Cal(a)，大家都懂吧（算了，复制一遍吧<<((因为当前的Cal(k)是计算出从1到k-1的符合条件的数的个数，所以要计算a~b的个数要用Cal(b+1)-Cal(a).))>>）

f[i][j]定义一样，以j开始的且符合条件的总位数为i的答案个数.（好绕啊）

预处理转移不用讲吧：f[i][j]+=f[i-1][k];（还是复制了）

有个小细节，每个一位数答案都为1，所以分f[1][j]=0.

重点讲讲不同之处（Cal函数）：

显然位数比x要小的数字都是合法的都在[1,x）区间内，直接统计就行.(第一次加ans)

位数和x一样最高位的数字比x小的数字都是合法的都在[1,x）区间内直接统计就行(第二次加ans)

位数和x一样，最高位又和x一样我们从左到右扫一遍x各个位子上的数字大小然后枚举合法的该位子上的数[0,9]判断是否合法就行。(第三次加ans)

#include<bits/stdc++.h>

using namespace std;

int f[][];

int a,b;

int digit[],cnt,ans;

void init ()

{

    for (int i=;i<=;i++) f[][i]=;

    for (int i=;i<=;i++)

    for (int j=;j<=;j++)

    for (int k=;k<=;k++)

    if(abs(j-k)>=)

    f[i][j]+=f[i-][k];

}

int Cal(int x)

{

    //freopen("a.in", "r", stdin);

    memset(digit,,sizeof(digit));

    ans=;

    cnt=;

    while(x)

    {

        digit[++cnt]=x%;

        x/=;

    }

    //三种情况

    for (int i=;i<cnt;i++)

    for (int j=;j<=;j++)

    ans+=f[i][j];        //在不到x位数前，所有情况符合。

    for (int i=;i<digit[cnt];i++)  ans+=f[cnt][i];      //x位数，最高位未到digit[cnt]。

    for (int i=cnt-;i>=;i--)//x位数，最高位到digit[cnt]

    {

        for (int j=;j<digit[i];j++)

        if(abs(j-digit[i+])>=)

        ans+=f[i][j];

        if(abs(digit[i]-digit[i+])<)

        break;

    }

    //printf("%d\n",ans);

    return ans;

}

void work()

{

    cin>>a>>b;

    cout<<Cal(b+)-Cal(a)<<'\n';

}

int main()

{

    init();

    work();

    return ;

}