HDU2089 不要62 【数位DP】

tonyfang posted @ 2015年8月15日 10:58 in HDU with tags c++ HDU , 393 阅读

上一次次讲了数位DP,这次来复习下。

HDU2089:不要62:传送门这里

这题嘛,也是比较简单的。

首先还是和原来一样的$f_{i,j}$表示$i$位,最高位为$j$的吉利数的数量。

那么转移也是差不多的,枚举$i-1$位的时候的最高位$k$,然后根据情况进行转移就行了。

统计的时候也是一样,我们$calc(a)$函数统计$(0,a)$,那么首先分解$a$的每位数,然后从高往低逐位进行统计就行啦。

代码十分的简单啦

 

# include <stdio.h>
using namespace std;
int f[10][10];
int a,b;

int calc(int n) {
    int m=0,ans=0,A[10];
    while(n) {
        A[++m]=n%10;
        n/=10;
    }
    A[m+1]=0;
    for (int i=m;i>=1;--i) {
        for (int j=0;j<A[i];++j) 
            if(j!=4&&!(A[i+1]==6&&j==2)) ans+=f[i][j];
        if(A[i]==4||(A[i+1]==6&&A[i]==2)) break;
     }
     return ans;
}

int main() {
    f[0][0]=1;
    for (int i=1;i<=8;++i) {
        for (int j=0;j<10;++j)
            for (int k=0;k<10;++k) {
                if(j!=4&& !(j==6&&k==2)) f[i][j]+=f[i-1][k];
            }
    }
    while(scanf("%d%d",&a,&b)!=EOF&&(a+b)) printf("%d\n",calc(b+1)-calc(a));
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter