2017"百度之星"程序设计大赛 - 复赛1005&&HDU 6148 Valley Numer【数位dp】
2024-08-26 07:03:57
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代码：
import java.util.Scanner;
public class Main {
/**
* @param args
*/
public static long MOD = 1000000007L;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String t = sc.nextLine();
int T = Integer.parseInt(t);
while (T-- != 0){
String N = sc.nextLine();
long[][][][] dp = new long[220][10][2][2];
int tnum = N.charAt(0) - '0';
for(int i = 1; i < tnum ; i++){
dp[0][i][0][0] = 1;
}
dp[0][tnum][1][0] = 1;
int len = N.length() -1;
for(int i = 1 ; i <= len ; i++){
tnum = N.charAt(i) - '0';
for(int j = 0 ; j < 10 ; j ++){
if(j !=0 ){
dp[i][j][0][0] ++;
dp[i][j][0][0] %= MOD;
}
for(int k = 0 ; k < 10 ;k ++){
if(j <= k){
dp[i][j][0][0] += dp[i-1][k][0][0];
if(j < tnum){
dp[i][j][0][0] += dp[i-1][k][1][0];
}
dp[i][j][0][0] %= MOD;
}
if(j >= k){
dp[i][j][0][1] += dp[i-1][k][0][1];
if(j < tnum){
dp[i][j][0][1] += dp[i-1][k][1][1];
}
dp[i][j][0][1] %= MOD;
}
if(j > k){
dp[i][j][0][1] += dp[i-1][k][0][0];
if(j < tnum){
dp[i][j][0][1] += dp[i-1][k][1][0];
}
dp[i][j][0][1] %= MOD;
}
if(j == tnum){
if(j <= k){
dp[i][j][1][0] += dp[i-1][k][1][0];
dp[i][j][1][0] %= MOD;
}
if(j >= k){
dp[i][j][1][1] += dp[i-1][k][1][1];
dp[i][j][0][1] %= MOD;
}
if(j > k){
dp[i][j][1][1] += dp[i-1][k][1][0];
dp[i][j][0][1] %= MOD;
}
}
}
}
}
long ans = 0;
for(int i = 0; i < 10; i++){
ans += dp[len][i][0][0];
ans += dp[len][i][0][1];
ans += dp[len][i][1][0];
ans += dp[len][i][1][1];
ans %= MOD;
}
System.out.println(ans);
}
}
}
最新文章
- 在一个项目各个子模块中使用Maven的一些通用的准则
- iOS工作小技巧及填坑记录
- Emoji表情符号录入MySQL数据库报错
- PHP 表单验证--安全性--小记
- Android优化—— Google 发布 Android 性能优化典范
- Javascript 基础（二）
- 【3】Bootstrap的下载和目录结构
- 后续遍历 java leecode
- 【TFS】增加组员，以及用户权限分配
- grasp设计模式笔记回顾
- Java反射机制示例
- Zepto源码分析（二）奇淫技巧总结
- P1352 没有上司的舞会
- 使用appium做自动化测试时，send_keyss只能输入字母数字，无法输入中文
- Halcon示例：print_quality 字符验证
- jenkins安装Scanner插件
- centos6.5环境通达OA数据库mysql5.0.67升级至mysql5.5.48方案
- 小学生都能写智能语音助手了，我这颗转战AI的心要何去何从？
- 通过sqli-labs学习sql注入——基础挑战之less1
- mongodb基本使用（一）