BZOJ 1026: [SCOI2009]windy数 – [数位DP]


题目传送门(BZOJ)
>原文链接<

题解 :

从L到R可以直接转化成前缀求和相减.

状态 :

F[i][j]表示i位数中结尾为j的数字有多少

转移 :

F[i][j] = \sum F[i-1][k] \;\;\;[abs(k-j)\ge2]

求答案 :

对于一个数x, 我们先按位分解之. 设第i位为X[i] ,个位为第一位.

x的位数是sum , 则\sum\limits_{i=1}^{sum-1}\sum\limits_{j=1}^{9}F[i][j]可以被累加到答案中

同时, \sum\limits_{i=1}^{X[sum]-1}F[sum][i]也要被累加到答案中.

剩下的, 就是对于每一位, 看他能取到多少, 累加到答案中, 有几个特判, 不方便写进式子:

sum-1开始枚举每一位i, 再枚举一个j0X[i], 当abs(j-X[i+1])\ge 2, F[i][j] 可以被累加到答案中

i = 1时, 对于每个可行的j, 我们还要多累加一个1到答案中.

代码 :

#include 
#include 
#include 
using namespace std;
int f[11][10];
int l,r;
void init() {
    int i,j,k;
    for(i=0;i<=9;i++) f[1][i]=1;
    for(i=2;i<=10;i++)
        for(j=0;j<=9;j++)
            for(k=0;k<=9;k++)
                if(abs(j-k)>=2)
                    f[i][j]+=f[i-1][k];
}
int work(int x) {
    if(!x)return 0;
    int ret = 0;
    int sum = 0;
    int que[15];
    int i,j;
    memset(que,0,sizeof que);
    while(x) {
        que[++sum]=x%10;
        x/=10;
    }
    for(i=1;i=1;i--) {
        for(j=0;j=2)
                ret+=f[i][j];
        }
        if(abs(que[i+1]-que[i])<2)break;
        if(i==1)ret++;
    }
    return ret;
}
int main() {
    init();
    scanf("%d%d",&l,&r);
    printf("%d\n",work(r)-work(l-1));
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注