首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【HDU-6148】 Valley Numer(数位dp)

【HDU-6148】 Valley Numer(数位dp)

作者头像
饶文津
发布2020-06-02 16:02:16
2890
发布2020-06-02 16:02:16
举报
文章被收录于专栏:饶文津的专栏饶文津的专栏

百度之星2017复赛1005 HDU-6148 Valley Numer

题意

不出现上升后直接下降数位的数,不超过n的有几个。前导零不算。

题解

dfs(当前数位的位置len,这位的数num,是否在上升up,是否有限制limit) limit不用存到状态里,因为limit为true时不可能访问两次。 num=-1代表还没开始这个数的第一位,前面是前导零。 up=1时,不允许下降。

代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define N 105
const ll M = 1e9+7;
using namespace std;

int t;
char s[N];
int mlen;
ll st[N][11][2];
void add(ll &x,ll v){
    x+=v;if(x>=M)x-=M;
}
ll dfs(int len,int num,int up,bool limit);
void work(int len,int num,int up,bool limit,int i,ll &ans){
    if(num==-1 && i==0){
        add(ans,dfs(len+1,-1,0,limit));
    }else{
        if(num==-1){
            add(ans,dfs(len+1,i,0,limit));
        }else if(i<num){
            if(up==0)
            add(ans,dfs(len+1,i,0,limit));
        }else if(i==num){
            add(ans,dfs(len+1,i,up,limit));
        }else{
            add(ans,dfs(len+1,i,1,limit));
        }
    }
}
ll dfs(int len,int num,int up,bool limit){
    if(len==mlen) return num != -1;
    if(!limit && (~num)&&(~st[len][num][up]))return st[len][num][up];
    ll ans=0;
    int b=limit?s[len]-'0':9;
    for(int i=0;i<=b;++i)
        work(len,num,up,i==b&&limit,i,ans);
    return num<0||limit?ans:st[len][num][up]=ans;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%s",s);
        mlen=strlen(s);
        mem(st,-1);
        printf("%lld\n",dfs(0,-1,0,1));
    }
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-08-18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • 题解
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档