开发者社区> angel_kitty> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

2017"百度之星"程序设计大赛 - 复赛1005&&HDU 6148 Valley Numer【数位dp】

简介: 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 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 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
2021 年百度之星·程序设计大赛 - 初赛一、二
2021 年百度之星·程序设计大赛 - 初赛一、二
0 0
2017"百度之星"程序设计大赛 - 复赛1003&&HDU 6146 Pok&#233;mon GO【数学,递推,dp】
Pokémon GO Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 171    Accepted Submission(s): 104 Problem Description 众所周知,度度熊最近沉迷于 Pokémon GO。
1185 0
2017"百度之星"程序设计大赛 - 复赛1001&&HDU 6144 Arithmetic of Bomb【java大模拟】
Arithmetic of Bomb Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 129    Accepted Submission(s): 94 Problem Description 众所周知,度度熊非常喜欢数字。
896 0
2017"百度之星"程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集),1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】
度度熊保护村庄 Accepts: 13 Submissions: 488 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description 哗啦啦村袭击了喵哈哈村! 度度熊为了拯救喵哈哈村,带着自己的伙伴去救援喵哈哈村去了!度度熊与伙伴们很快的就过来占据了喵哈哈村的各个军事要地,牢牢的守住了喵哈哈村。
1330 0
破壁人AI百度:科技公司反内卷的典型样本
互联网整个行业都在陷入被动且尴尬的局面。去年开始流行的“内卷”一词,恰如其分的描述了互联网的现状,比如抖音开始做外卖,微信强推视频号,一直硝烟弥漫的电商市场,更是激战在社区团购上
0 0
百度飞桨学院神奇AI技术
百度飞桨学院神奇AI技术
0 0
+关注
angel_kitty
我叫Angel_Kitty,当然你也可以叫我笔名,Sakura,喜欢交友,乐于助人,喜欢音乐,热爱ACM竞赛,CTF竞赛,喜欢算法、Web、网络安全、黑科技、机器学习、数学建模,C/C++、C#、Java、Python、HTML5、JavaScript,E都略懂,现在主攻逆向工程
文章
问答
文章排行榜
最热
最新
相关电子书
更多
百度大规模时序指标自动异常检测实战
立即下载
从百度文件系统看大型分布式系统设计
立即下载
百度万人研发团队 Git 工具链建设的挑战与思考
立即下载