# 数位DP入坑

Hdu 2089 不要62

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

inline int read()

{

    char c=getchar();int num=;

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar())

        num=num*+c-'';

    return num;

}

const int N=1e6+;

int n,m;

int a[],dgt;

int f[][;

int dfs(int dep,int pre,int sta,bool lim)

{

    if(!dep)

        return ;

    if(!lim&&f[dep][sta!=-)

        return f[dep][sta];

    int up=lim?a[dep]:;

    int ans=;

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

    {

        if(i==) continue;

        if(pre==&&i==) continue;

        ans+=dfs(dep-,i,i==,lim&&i==a[dep]);

    }

    if(!lim)

        f[dep][sta]=ans;

    return ans;

}

int solve(int x)

{

    for(dgt=;x;a[++dgt]=x%,x/=);

    return dfs(dgt,,,);

}

int main()

{

    while()

    {

        memset(f,-,sizeof(f));

        n=read(),m=read();

        if(!n&&!m)

            break;

        cout<<solve(m)-solve(n-)<<'\n';

    }

    return ;

}

Hdu 6148 Valley Numer

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

inline int read()

{

    char c=getchar();int num=;

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar())

        num=num*+c-'';

    return num;

}

const int N=;

const int mod=1e9+;

int T,n;

char a[N];

int f[N][][];

int dfs(int dep,int pre,int turn,bool lim,bool invalid)

{

    if(dep==n+)

        return invalid?:;

    if(!lim&&f[dep][pre][turn]!=-)

        return f[dep][pre][turn];

    int up=lim?a[dep]-='':;

    int ans=;

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

    {

        if(turn==&&i<pre)

            continue;

        int p=;

        if(invalid) p=;

        else if(i>pre) p=;

        else if(i<pre) p=;

        else p=turn;

        ans+=dfs(dep+,i,p,lim&&i==a[dep],invalid&&i==);

        ans%=mod;

    }

    if(!lim)

        f[dep][pre][turn]=ans;

    return ans;

}

int main()

{

    T=read();

    while(T--)

    {

        memset(f,-,sizeof(f));

        scanf("%s",a+);

        n=strlen(a+);

        cout<<dfs(,,,,)<<'\n';

    }

    return ;

}

Bzoj 1026: [SCOI2009]windy数

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

inline LL read()

{

    char c=getchar();LL num=;

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar())

        num=num*+c-'';

    return num;

}

LL A,B;

LL a[],dgt;

LL f[][];

LL dfs(int dep,int pre,bool lim,bool invalid)

{

    if(!dep)

        return invalid?:;

    if(!lim&&!invalid&&f[dep][pre]!=-)

        return f[dep][pre];

    int up=lim?a[dep]:;

    LL ans=;

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

    {

        if(!invalid&&abs(i-pre)<) continue;

        ans+=dfs(dep-,i,lim&&i==a[dep],invalid&&i==);

    }

    if(!lim&&!invalid)

        f[dep][pre]=ans;

    return ans;

}

LL solve(LL x)

{

    for(dgt=;x;a[++dgt]=x%,x/=);

    return dfs(dgt,,,);

}

int main()

{

    A=read(),B=read();

    memset(f,-,sizeof(f));

    cout<<solve(B)-solve(A-);

    return ;

}

Poj 3252  Round Numbers

题意：问[l,r]中二进制位1比0少的数有多少个。

Sol: 记录当前层0,1个数。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

inline int read()

{

    char c=getchar();int num=;

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar())

        num=num*+c-'';

    return num;

}

int l,r;

int a[],bit;

int f[][][];

int dfs(int dep,int c0,int c1,bool lim,bool invalid)

{

    if(!dep)

        return (!invalid&&c0>=c1)?:;

    if(!lim&&f[dep][c0][c1]!=-)

        return f[dep][c0][c1];

    int up=lim?a[dep]:;

    int ans=;

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

        ans+=dfs(dep-,c0+(i==&&!invalid),c1+(i==),lim&&i==up,invalid&&i==);

    if(!lim)

        f[dep][c0][c1]=ans;

    return ans;

}

int solve(int x)

{

    for(bit=;x;a[++bit]=x&,x>>=);

    return dfs(bit,,,,);

}

int main()

{

    memset(f,-,sizeof(f));

    l=read(),r=read();

    cout<<solve(r)-solve(l-);

    return ;

}

P2518 [HAOI2010]计数

一个比较假的数位DP？但也是按照数位来做的。

Sol:无。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

inline int read()

{

    char c=getchar();int num=;

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar())

        num=num*+c-'';

    return num;

}

char num[];

LL ans;int n,m;

int a[],cnt[];

LL c[][];

void init()

{

    c[][]=;

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

    {

        c[i][]=;

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

            c[i][j]=c[i-][j-]+c[i-][j];

    }

}

LL C(int n)

{

    LL res=;

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

        if(cnt[i])

            res*=c[n][cnt[i]],n-=cnt[i];

    return res;

}

int main()

{

    init();

    scanf("%s",num+);

    for(n=;num[n];++n)

        a[n]=num[n]-'',++cnt[num[n]-''];

    m=--n;

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

    {

        --m;

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

            if(cnt[j])

                --cnt[j],ans+=C(m),++cnt[j];

        --cnt[a[i]];

    }

    cout<<ans;

    return ;

}