Valley Numer

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 311 Accepted Submission(s): 165

Problem Description

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

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

当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 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,可以将状态设计成四维

当前数字长度len最后一位数字digit;是否已经在递增序列里increased是否和当前前缀相同same_prefix

转移时处理好这些状态就好了。

java代码，还望dalao们海涵QAQ

下面给出AC代码：

1 import java.util.Scanner; 2  3  4 public class Main { 5  6     /** 7      * @param args 8      */ 9         public static long MOD = 1000000007L;10         public static void main(String[] args) {11             Scanner sc = new Scanner(System.in);12             String t = sc.nextLine();13             int T = Integer.parseInt(t);14             while (T-- != 0){15                 String N = sc.nextLine();16                 long[][][][] dp = new long[220][10][2][2];17                 int tnum = N.charAt(0) - '0';18                 for(int i = 1; i < tnum ; i++){19                     dp[0][i][0][0] = 1;20                 }21                 dp[0][tnum][1][0] = 1;22                 int len = N.length() -1;23                 for(int i = 1 ; i <= len ; i++){24                     tnum = N.charAt(i) - '0';25                     for(int j = 0 ; j < 10 ; j ++){26                         if(j !=0 ){27                             dp[i][j][0][0] ++;28                             dp[i][j][0][0] %= MOD;29                         }30                         for(int k = 0 ; k < 10 ;k ++){31                             if(j <= k){32                                 dp[i][j][0][0] +=  dp[i-1][k][0][0];33                                 if(j < tnum){34                                     dp[i][j][0][0] += dp[i-1][k][1][0];35                                 }36                                 dp[i][j][0][0] %= MOD;37                             }38 39                             if(j >= k){40                                 dp[i][j][0][1] +=  dp[i-1][k][0][1];41                                 if(j < tnum){42                                     dp[i][j][0][1] += dp[i-1][k][1][1];43                                 }44                                 dp[i][j][0][1] %= MOD;45                             }46 47                             if(j > k){48                                 dp[i][j][0][1] +=  dp[i-1][k][0][0];49                                 if(j < tnum){50                                     dp[i][j][0][1] += dp[i-1][k][1][0];51                                 }52                                 dp[i][j][0][1] %= MOD;53                             }54 55                             if(j == tnum){56                                 if(j <= k){57                                     dp[i][j][1][0] +=  dp[i-1][k][1][0];58                                     dp[i][j][1][0] %= MOD;59 60                                 }61                                 if(j >= k){62                                     dp[i][j][1][1] +=  dp[i-1][k][1][1];63                                     dp[i][j][0][1] %= MOD;64                                 }65 66                                 if(j > k){67                                     dp[i][j][1][1] +=  dp[i-1][k][1][0];68                                     dp[i][j][0][1] %= MOD;69                                 }70                             }71                         }72                     }73                 }74 75                 long ans = 0;76                 for(int i = 0; i < 10; i++){77                     ans += dp[len][i][0][0];78                     ans += dp[len][i][0][1];79                     ans += dp[len][i][1][0];80                     ans += dp[len][i][1][1];81                     ans %= MOD;82                 }83                 System.out.println(ans);84             }85         }86 }