Java 第十一届 蓝桥杯 省模拟赛 正整数的摆动序列
2023-09-14 08:58:02 时间
正整数的摆动序列
问题描述
如果一个序列的奇数项都比前一项大,偶数项都比前一项小,则称为一个摆动序列。即 a[2i]<a[2i-1], a[2i+1]>a[2i]。
小明想知道,长度为 m,每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。
输入格式
输入一行包含两个整数 m,n。
输出格式
输出一个整数,表示答案。答案可能很大,请输出答案除以10000的余数。
样例输入
3 4
样例输出
14
样例说明
以下是符合要求的摆动序列:
2 1 2
2 1 3
2 1 4
3 1 2
3 1 3
3 1 4
3 2 3
3 2 4
4 1 2
4 1 3
4 1 4
4 2 3
4 2 4
4 3 4
评测用例规模与约定
对于 20% 的评测用例,1 <= n, m <= 5;
对于 50% 的评测用例,1 <= n, m <= 10;
对于 80% 的评测用例,1 <= n, m <= 100;
对于所有评测用例,1 <= n, m <= 1000。
这里附上亓老板的提高时间效率的一些[小技巧](https://blog.csdn.net/qq_43422111/article/details/105326623)
package 省模拟赛;
import java.util.Scanner;
public class 正整数的摆动序列 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
sc.close();
//dp[i][j] i表示第多少位,j表示一个分界线
// 奇数行就是大于j的方案数,偶数行就是小于j的方案数
// 奇数要比前面的大,所以要大于的,偶数要比前面的小,所以要小于的
int[][] dp = new int[m+2][n+2];
//初始化边界
for (int i = 1; i <=n; i++) {
dp[1][i]=n-i+1;
}
for(int i = 2; i <= m; i++)
if((i&1)==1){
//奇数的话是要比前面大的,所以用倒序
for(int j = n; j >= 1; j--){
dp[i][j] = (dp[i-1][j-1] + dp[i][j+1]) % 10000;
}
}
else{
for(int j = 1; j <= n; j++){
dp[i][j] = (dp[i-1][j+1] + dp[i][j-1]) % 10000;
}
}
//判断奇偶从此我要改成这个了,一位位运算确实快
//m&1,就是把m换成二进制看看最后一位是不是1,如果是1证明就是奇数,如果是0证明是偶数
int result = (m & 1)==1 ? dp[m][1] : dp[m][n];
System.out.println(result);
}
}
相关文章
- dos命令运行java代码_如何制作ddos攻击
- java怎么调用.asmx_Java调用Webservice(asmx)的例子
- java工具类-Java对象转换成Map
- 怎么下载java_怎样下载Java的环境?
- java笔记–Map的用法
- java验证手机号正则表达式_Java使用正则表达式验证手机号和电话号码的方法「建议收藏」
- java 缓存工具类初始化_Java缓存框架
- Java基于ssm师生实验课-实验室-实验设备预约系统源码
- java.lang.Exception: libsvm classes not in CLASSPATH!问题解决方法详解大数据
- Java 反射工具类详解编程语言
- java cookie操作的封装 常用判断方法的封装详解编程语言
- java发送http的get、post请求详解编程语言
- Java的对象初始化过程详解编程语言
- 从零开始学Java和MySQL(javamysql教程)
- 时间控制Java运用Redis实现过期时间控制(redisjava过期)
- 时间设置Java使用Redis设置过期时间(redisjava过期)
- 策略Java实现Redis过期策略的优化实践(redisjava过期)
- Oracle全面支持Java链技术构建数据库应用(java链oracle)
- 实现基于Redis的分布式锁Java实现(redis锁java代码)
- 缓存使用Redis让Java代码更加迅速缓存设置(redis设置java)
- Java中实现随机无重复数字的方法
- java读取excel文件并复制(copy)文件到指定目录示例