Java 第十一届蓝桥杯省模拟赛正整数的摆动序列

客官°小女子只卖身不卖艺 2023-07-25 08:47 117阅读 0赞

## 正整数的摆动序列 ##

问题描述

如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a\[2i\]<a\[2i-1\], a\[2i+1\]>a\[2i\]。  
　　小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。

输入格式

输入一行包含两个整数 m，n。

输出格式

输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。

样例输入

3 4

样例输出

样例说明

以下是符合要求的摆动序列：  
　　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);
    		
    	}
    }