BZOJ1026: [SCOI2009]windy数 ( 数位dp )

2021-05-01 15:27

阅读：412

标签：geo turn int name 技术分享 iostream printf continue img

传送门

嗯比前面两道都简单...其实这是我第一道写的数位dp...非常基础了...

依然是码代码....

我的代码...怎么这么丑呢....

 1 #include 2 #include 3 #include 4 #include 5 #include
 6 #include 7 using namespace std;
 8 long long a,b;
 9 int shu[20]={};
10 int f[20][20]={};
11 int abv(int x){
12     if(x>0){
13         return x;
14     }
15     return -x;
16 }
17 int dfs(int k,int num,bool shang){
18     if(k0){
19         return 1;
20     }
21     if((!shang)&&num>=0&&f[k][num]!=-1){
22         return f[k][num];
23     }
24     int ans=0,p,maxn=shang?shu[k]:9;
25     for(int i=0;i){
26         if(abv(i-num)2){
27             continue;
28         }
29         p=i;
30         if(i==0&&num==-5){
31             p=num;
32         }
33         ans+=dfs(k-1,p,shang&&i==maxn);
34     }
35     if(!shang){
36         f[k][num]=ans;
37     }
38     return ans;
39 }
40 int solve(long long x){
41     memset(shu,0,sizeof(shu));
42     int k=0;
43     while(x){
44         shu[++k]=x%10;
45         x/=10;
46     }
47     return dfs(k,-5,1);
48 }
49 int main(){
50     scanf("%lld%lld",&a,&b);
51     memset(f,-1,sizeof(f));
52     printf("%d\n",solve(b)-solve(a-1));
53     return 0;
54 }

View Code

BZOJ1026: [SCOI2009]windy数 ( 数位dp )

标签：geo turn int name 技术分享 iostream printf continue img

原文地址：http://www.cnblogs.com/137shoebills/p/7783876.html

上一篇：Win10下 tensorflow gpu版安装

下一篇：Windows server 2012公用网络修改为专用网络

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ1026: [SCOI2009]windy数 ( 数位dp )
文章链接：http://soscw.com/index.php/essay/80919.html

亲，登录后才可以留言！

BZOJ1026: [SCOI2009]windy数 ( 数位dp )

评论

热门文章

推荐文章

最新文章

置顶文章