BZOJ 1026 [SCOI2009] windy 디지털 DP?

제목:링크

방법: 디지털 DP?

해석: 디지털 DP 개 귀신, 분명히 디지털 추이

우선 이 데이터 범위에 대해 O(1)는 통과할 수 있습니까?

다시 생각해 보면 틀렸어, 9 번이 제일 크면 9 명이야!

그래서 일종의 상태를 생각할 수 있다. f[i][j]는 길이가 i이고 첫 번째가 j인 windy수이다.

그 다음에 f[i][j]=∑f[i-3-1][k]와 abs(k-3j)>=2

그다음에 디테일 코드가 위치별로 처리가 됐어요.

근데 저 질문 있어요. 여보세요.

왜 내 모든 것은 한 사람만 계산이 틀렸지?다른 분은 맞으시죠?

그래서 나는 좀 파렴치할 수밖에 없었다. 가트판은 1~9번 물어보면 바로 자신에게 돌아간다.

먼저 구덩이를 파다.

코드:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f[15][15];
int bit[15];
void init()
{
    for(int i=0;i<=9;i++)f[1][i]=1;
    for(int i=2;i<=10;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
            }
        }
    }
}
int cal(int x)
{
    if(x<10)return x;
    if(!x)return 0;
    int s_bit=10,ans=0;
    while(bit[s_bit]>x)s_bit--;
    for(int i=1;i<s_bit;i++)
    {
        for(int j=1;j<=9;j++)
        {
            ans+=f[i][j];
        }
    }
    int aft=x/bit[s_bit];
    x%=bit[s_bit];
    for(int i=1;i<aft;i++)ans+=f[s_bit][i];
    int pre_bit=aft;
    for(int i=s_bit-1;i;i--)
    {
        int bit_now=x/bit[i];
        if(i!=1)
        {
            for(int j=0;j<bit_now;j++)
            {
                if(abs(pre_bit-j)>=2)ans+=f[i][j];
            }
        }else
        {
            for(int j=0;j<=bit_now;j++)
            {
                if(abs(pre_bit-j)>=2)ans+=f[i][j];
            }
        }
        if(abs(pre_bit-bit_now)<2)break;
        pre_bit=bit_now;
        x%=bit[i];
    }
    return ans;
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    init();
    bit[1]=1;
    for(int i=2;i<=10;i++)bit[i]=bit[i-1]*10;
    cal(1);
    printf("%d
",cal(b)-cal(a-1));
}