1026: [SCOI2009]windy数

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1026

数位dp。f[i][j]表示i位数最高位为j的windy数个数。
可以将问题转化为求0~n的windy数个数。
设n为m位数，则可以先求出1~m-1位数的windy数个数，然后计算m位数。
从高位往低位计算（这样上一位是确定的），需要注意的是检查上一位和上上位，看是否满足windy数，不满足可以直接退出。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
const int MaxN=15;

int n;
long long f[MaxN][10],a,b;

long long work(long long a)
{
    if (a<0)
    {
        return 0;
    }
    if (a==0)
    {
        return 1;
    }
    int n=(int)log10(a)+1;
    long long tot=1;
    for (int i=1;i<n;i++)
    {
        for (int j=1;j<=9;j++)
        {
            tot+=f[i][j];
        }
    }
    int last=-2;
    long long p=1;
    bool flag=0;
    if (n==1)
    {
        flag=1;
    }
    for (;n!=0;a%=p,n--)
    {
        long long t=a;
        p=1;
        for (int i=0;i<n-1;i++)
        {
            t/=10;
            p*=10;
        }
        for (int i=0;i<t;i++)
        {
            if (i==0 && flag==0)
            {
                continue;
            }
            if (abs(i-last)>1)
            {
                tot+=f[n][i];
            }
        }
        if (n==1)
        {
            if (abs(t-last)>1)
            {
                tot++;
            }
        }
        if (abs(last-t)<=1)
        {
            break;
        }
        last=t;
        flag=1;
    }
    return tot;
}

void treat()
{
    for (int i=0;i<=9;i++)
    {
        f[1][i]=1;
    }
    for (int i=2;i<=n;i++)
    {
        for (int j=0;j<=9;j++)
        {
            f[i][j]=0;
            for (int k=0;k<=9;k++)
            {
                if (abs(j-k)>1)
                {
                    f[i][j]+=f[i-1][k];
                }
            }
        }
    }
}

int main()
{
    cin>>a>>b;
    a--;
    n=log10(b)+1;
    treat();
    cout<<work(b)-work(a)<<endl;
    return 0;
}

posted on 2013-02-13 14:45 Kiro 阅读(96) 评论(0)  编辑 收藏 引用 所属分类: 衡八oj

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理