第一题就是求众数 投票法a掉
第二题抽卡序列 动规解
题目描述：初始位置0已有卡片0，现在有1~n的卡片，从卡牌中随机抽一张出来加入末尾，求满足下面条件的卡牌序列有多少种1、最末尾位置为卡片n2、相邻两位置卡片数字的差值绝对值大小不超过2
输入 3输出 2解释： 有2个合法的序列 {0,1,2,3}、{0,2,1,3}
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
int MOD = 998244353;
for(int i = 4;i < n + 1;i++){
dp[i] = (dp[i-1] + dp[i-3])%MOD;
}
System.out.println(dp[n]);
}
}
简单说下我的思路，以i结尾的序列可以由i-1、i-3计算到
i-1非常直观 直接在dp[i-1]的每个序列后 添加一个i就可以
但是这种添加的方法实际上限定了最后两个位置分别是i-1，i
实际上最后2个位置还可以是i-2,i
所以在dp[i-3]的所有序列后面固定添加{i-1,i-2,i}的序列也是解
即dp[i] = dp[i-1]+dp[i-3]
全部评论
(13) 回帖