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 }