2020 蓝桥杯校内模拟赛 F. 满足条件的正整数序列（dp）

我不是女神ヾ 2023-07-17 11:21 19阅读 0赞

**问题描述**

小明想知道，满足以下条件的正整数序列的数量：
    　　1. 第一项为 n；
    　　2. 第二项不超过 n；
    　　3. 从第三项开始，每一项小于前两项的差的绝对值。
    　　请计算，对于给定的 n，有多少种满足条件的序列。

**输入格式**

输入一行包含一个整数 n。

**输出格式**

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

**样例输入**

**样例输出**

**样例说明**

以下是满足条件的序列：
    　　4 1
    　　4 1 1
    　　4 1 2
    　　4 2
    　　4 2 1
    　　4 3
    　　4 4

**评测用例规模与约定**

对于 20% 的评测用例，1 <= n <= 5；
    　　对于 50% 的评测用例，1 <= n <= 10；
    　　对于 80% 的评测用例，1 <= n <= 100；
    　　对于所有评测用例，1 <= n <= 1000。

**思路：** 用 dp\[i\]\[j\] 表示以 i 、j 为前两项，能衍生出的子序列的个数。比如以 41 为前两项，那么他的子序列有 411、412，其本身 41 也是一种子序列。故可以得出状态转移方程：dp\[i\]\[j\] = dp\[j\]\[1\] + … + dp\[j\]\[abs(i-j)-1\] + 1（ij 本身）。

**Code：**

import java.util.Scanner;
    public class Main { 
    	static int mod = 10000;
    	static int[][] dp = new int[1010][1010];
    	static int countSep(int first,int second) { 
    		if(dp[first][second]!=-1)
    			return dp[first][second];
    		int cnt=1;
    		for(int i=1;i<Math.abs(first-second);i++)
    			cnt+=countSep(second,i);
    		dp[first][second]=cnt%mod;
    		return dp[first][second];
    	}
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    		for(int i=1;i<=1000;i++)
    			for(int j=1;j<=1000;j++)
    				dp[i][j] = -1;
    		Scanner cin = new Scanner(System.in);
    		int n = cin.nextInt();
    		dp[1][1] = 1;
    		int ans=0;
    		for(int i=1;i<=n;i++)
    			ans = (ans+countSep(n,i))%mod;
    		System.out.println(ans);
    	}
    }