[BZOJ1026][SCOI2009]windy数（数位dp）

题目描述

传送门

题解

状态：f(i,j)表示i位数，第i位是j，每位相差至少为2的数的个数
转移： if (Abs(j,k)>=2) f[i][j]+=f[i-1][k];
注意：这道题处理前导0的情况比较吃屎，这里的转移方程是不包括前导0的情况，我的处理方法是在求解的时候单独算。
细节也比较多。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int n,m,f[20][20],g[20][20],digit[20];
inline int Abs(int a,int b){return (a>b)?a-b:b-a;}
inline void dp(){
    for (int i=0;i<10;++i) f[1][i]=1;
    for (int i=0;i<10;++i) g[1][i]=1;
    for (int i=2;i<=10;++i)
      for (int j=0;j<10;++j)
        for (int k=0;k<10;++k)
          if (Abs(j,k)>=2)
            f[i][j]+=f[i-1][k];
}
inline int calc_ans(int n){
    int cnt=0,ans=0;memset(digit,0,sizeof(digit));
    while (n) digit[++cnt]=n%10,n/=10;

    for (int i=1;i<cnt;++i)
      for (int j=1;j<10;++j) 
        ans+=f[i][j];

    for (int i=cnt;i>=1;--i){
        for (int j=0;j<digit[i];++j)
          if (i==cnt&&!j) continue;
          else if (i==cnt||Abs(j,digit[i+1])>=2) ans+=f[i][j];

        if (i!=cnt&&Abs(digit[i],digit[i+1])<2) break;
    }
    return ans;
}

int main(){
    dp();
    scanf("%d%d",&n,&m);
    printf("%d\n",calc_ans(m+1)-calc_ans(n));
}

2016.11.8 update

题解

一个更强的做法。
f(i,j,k,0/1,0/1,0/1,0/1)表示前i位，第i位填j，是否两位之间相差至少为2，是否卡下界L，是否卡上界R，1~i是否全为前导0的数的个数。
转移的时候分别讨论有前导0和没有前导0的情况，剩下的就很简单了。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int n,L,R,ans;
int a[20],b[20],f[20][20][2][2][2][2];

int Abs(int x)
{
    return x>0?x:-x;
}
int main()
{
    scanf("%d%d",&L,&R);
    while (L)
    {
        a[++a[0]]=L%10;
        L/=10;
    }
    while (R)
    {
        b[++b[0]]=R%10;
        R/=10;
    }
    n=max(a[0],b[0]);
    for (int i=1;i<=n/2;++i) swap(a[i],a[n-i+1]);
    for (int i=1;i<=n/2;++i) swap(b[i],b[n-i+1]);
    for (int i=a[1];i<=b[1];++i)
        f[1][i][i==0?0:1][i==a[1]?1:0][i==b[1]?1:0][i==0?1:0]=1;
    for (int i=1;i<n;++i)
        for (int j=0;j<=9;++j)
            for (int k=0;k<=1;++k)
                for (int c=0;c<=1;++c)
                    for (int d=0;d<=1;++d)
                        for (int e=0;e<=1;++e)
                        {
                            int l,r;
                            if (c&&d) l=a[i+1],r=b[i+1];
                            else if (!c&&!d) l=0,r=9;
                            else if (!c) l=0,r=b[i+1];
                            else l=a[i+1],r=9;
                            for (int t=l;t<=r;++t)
                            {
                                if (!e)
                                    f[i+1][t][k&(Abs(t-j)>=2?1:0)][c&(t==a[i+1]?1:0)][d&(t==b[i+1]?1:0)][0]+=
                                    f[i][j][k][c][d][e];
                                else
                                    f[i+1][t][t==0?0:1][c&(t==a[i+1]?1:0)][d&(t==b[i+1]?1:0)][e&(t==0?1:0)]+=
                                    f[i][j][k][c][d][e];
                            }
                        }
    for (int j=0;j<=9;++j)
        for (int c=0;c<=1;++c)
            for (int d=0;d<=1;++d)
                ans+=f[n][j][1][c][d][0];
    printf("%d\n",ans);
}