phpok做网站教程,wordpress后台去掉左上角1个wordpress更新,wordpress设置权限,wordpress视频主题Problem: 蓝桥勇士 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题#xff0c;我们可以使用最长递增子序列#xff08;LIS#xff09;的思想来解决。我们可以定义一个数组dp#xff0c;其中dp[i]表示以第i个对手结束的最长挑战序列的长度。对于每一个对… Problem: 蓝桥勇士 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题我们可以使用最长递增子序列LIS的思想来解决。我们可以定义一个数组dp其中dp[i]表示以第i个对手结束的最长挑战序列的长度。对于每一个对手我们都尝试将其加入到所有在其之前的对手所能形成的挑战序列中如果当前对手的战力值大于前面对手的战力值那么就可以将其加入到挑战序列中更新dp[i]的值。最后我们只需要找出dp数组中的最大值就是小明最多会挑战的对手数量。 解题方法 1.初始化dp数组dp[i] 1表示每个对手都可以单独形成一个挑战序列。 2.从第二个对手开始遍历其之前的所有对手如果当前对手的战力值大于前面对手的战力值那么就尝试将其加入到挑战序列中更新dp[i]的值dp[i] max(dp[i], dp[j] 1)。 3.遍历dp数组找出最大值即为小明最多会挑战的对手数量。 复杂度
时间复杂度: 遍历所有对手对于每个对手都需要遍历其之前的所有对手所以时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 空间复杂度: 我们需要一个长度为n的dp数组来存储状态所以空间复杂度为O(n)。 Code import java.util.*;
import java.io.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int n;static int MAXN 1010;static int[] arr new int[MAXN];static int[] dp new int[MAXN];public static void main(String[] args) throws IOException {n nextInt();for(int i 1; i n; i) {arr[i] nextInt();}for(int i 1; i n; i) {dp[i] 1;for(int j 1; j i; j) {if(arr[i] arr[j]) dp[i] Math.max(dp[i], dp[j] 1);}}int ans 0;for(int i 1; i n; i) {ans Math.max(dp[i], ans);}out.println(ans);out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}
}
