hdu6148 百度之星程序设计竞赛复赛 （数位dp）

时间：2023-12-10 17:06:26

Valley Numer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1402    Accepted Submission(s): 713

Problem Description
众所周知，度度熊非常喜欢数字。

它最近发明了一种新的数字：Valley Number，像山谷一样的数字。

hdu6148 百度之星程序设计竞赛复赛 （数位dp）

当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。

比如，1，10，12，212，32122都是 Valley Number。

121，12331，21212则不是。

度度熊想知道不大于N的Valley Number数有多少。

注意，前导0是不合法的。

Input
第一行为T，表示输入数据组数。

每组数据包含一个数N。

● 1≤T≤200

● 1≤length(N)≤100

Output
对每组数据输出不大于N的Valley Number个数，结果对 1 000 000 007 取模。
Sample Input
3
3
14
120
Sample Output
3
14
119
Source
思路：这应该算一道比较简单的数位dp题，数位dp入门题，刚学数位dp，还不是很熟，敲这题时，忘了考虑前导0的情况，参考了博客才知道自己错哪了。
定义一个dp[i][j][k]，i表示位置，j表示前一位，k表示单调性，0表示未知，1表示上升，2表示下降。
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<string>

#include<set>

#include<cmath>

#include<list>

#include<deque>

#include<cstdlib>

#include<bitset>

#include<stack>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-;

const ll mod=1e9+;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

string s;

ll a[],dp[][][];

ll dfs(int pos,int pre,int turn,bool limit,bool invalid)

{//pos为位置，turn为1表示上升，2下降，0未知，limit记录数位是否达上界，invalid记录前导是否都为0

    if(pos==-) return invalid?:;  //如果全部为0，不合法返回0，否则返回1

    if(!limit&&dp[pos][pre][turn]!=-)

        return dp[pos][pre][turn];   //被记忆过了

    int up=limit?a[pos]:;  //是否达上界

    ll ans=;

    for(int i=;i<=up;i++)

    {

        if(turn==&&i<pre) continue;

        int x;

        if(i==pre) x=turn;

        else if(i>pre) x=;

        else x=;

        if(invalid) x=;

        ans=(ans+dfs(pos-,i,x,limit&&i==a[pos],i==&&invalid))%mod;

    }

    if(!limit) dp[pos][pre][turn]=ans;  //记忆化

    return ans;

}

ll solve(string x)

{

    int pos=;

    for(int i=x.length()-;i>=;i--)

        a[pos++]=x[i]-'';

    return dfs(pos-,,,true,true);

}

int main()

{

    ios_base::sync_with_stdio(false); cin.tie();

    int T;

    cin>>T;

    while(T--)

    {

        string s;

        memset(dp,-,sizeof(dp));

        cin>>s;

        cout<<solve(s)<<endl;

    }

    return ;

}

相关文章