【BZOJ1026】【SCOI2009】windy数 数位DP

链接：

#include <stdio.h>
int main()
{
    puts("转载请注明出处[辗转山河弋流歌 by 空灰冰魂]谢谢");
    puts("网址：blog.csdn.net/vmurder/article/details/46446473");
}

题解：

f(i,j) 表示最高 i 位，此位为 j ，的方案数。
注意此数组存在前导零，比如 f(i,0) 。
f(i,j) 从 f(i−1,k) 随便转移。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 15
using namespace std;
long long f[N][N],g[N];
int long get(int x,int d,long long t,int c=-1)
{
    if(d==1)
    {
        int ret=0;
        for(int i=0;i<=x;i++)if(abs(i-c)>=2)
            ret++;
        return ret;
    }
    int i,ret=0;
    for(i=0;i<x/t;i++)if(abs(i-c)>=2)
        ret+=f[d][i];
    if(abs(x/t-c)<2)return ret;
    return ret+get(x%t,d-1,t/10,x/t);
}
int main()
{
// freopen("test.in","r",stdin);

    int i,j,k;
    int a,b,c;

    for(i=0;i<10;i++)f[1][i]=1;
    for(i=1;i<10;i++)for(j=0;j<10;j++)
        for(k=0;k<10;k++)if(abs(j-k)>=2)
            f[i+1][k]+=f[i][j];
    for(g[0]=i=1;i<=10;i++)
    {
        g[i]=g[i-1];
        for(j=1;j<10;j++)g[i]+=f[i-1][j];
    }

    int l,r;
    scanf("%d%d",&l,&r),l--;

    long long dl=1,tl=1;
    while(tl*10<=l)tl*=10,dl++;
    long long dr=1,tr=1;
    while(tr*10<=r)tr*=10,dr++;

    int ans=g[dr]-g[dl];
    if(r)ans+=get(r,dr,tr,dr==1?233:-1);
    if(l)ans-=get(l,dl,tl,dl==1?233:-1);
    printf("%d\n",ans);
    return 0;
}