AcWing 1010. 拦截导弹 原题链接
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于 3000030000 的正整数，导弹数不超过 10001000。
输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2
题目思路
第一问:最长不上升子序列，类比最长上升子序列
第二问：贪心问题
public static void main(String[] args) {
String s = in.nextLine();
String[] ss = s.split(" ");
int n = ss.length;
int[] arr = new int[n + 1];
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(ss[i - 1]);
int res1 = 0;
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (arr[j] >= arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res1 = Math.max(res1, dp[i]);
}
// store index
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
int k = -1;
for (int j = 0; j < list.size(); j++) {
if (arr[list.get(j)] >= arr[i]) {
k = j;
break;
}
}
if (k == -1) list.add(i);
else list.set(k, i);
}
int res2 = list.size();
out.println(res1);
out.println(res2);
out.flush();
out.close();
}
AcWing 187. 导弹防御系统 原题链接
为了对抗附近恶意国家的威胁，R国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如，一套系统先后拦截了高度为3和高度为4的两发导弹，那么接下来该系统就只能拦截高度大于4的导弹。
给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例，第一行包含整数n，表示来袭导弹数量。
第二行包含n个不同的整数，表示每个导弹的高度。
当输入测试用例n=0时，表示输入终止，且该用例无需处理。
输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。
数据范围
1≤n≤501≤n≤50
输入样例：
5
3 5 2 4 1
0
输出样例：
2
样例解释
对于给出样例，最少需要两套防御系统。
一套击落高度为3,4的导弹，另一套击落高度为5,2,1的导弹。
题目思路
暴搜每个点放在上升或者下降序列的情况
private static List<Integer> upSystem = new ArrayList<>();
private static List<Integer> downSystem = new ArrayList<>();
private static int res;
private static int[] arr;
private static void dfs(int total, int upNumber, int downNumber, int cur) {
if (res <= upNumber + downNumber) return;
if (total == cur) {
res = upNumber + downNumber;
return;
}
int k = -1;
for (int i = 0; i < upSystem.size(); i++) {
if (arr[upSystem.get(i)] > arr[cur]) {
k = i;
break;
}
}
//搜放在up system的情况
if (k == -1) {
upSystem.add(cur);
dfs(total, upNumber + 1, downNumber, cur + 1);
upSystem.remove(upSystem.size() - 1);
}else {
int temp = upSystem.get(k);
upSystem.set(k, cur);
dfs(total, upNumber, downNumber, cur + 1);
upSystem.set(k, temp);
}
//搜放在down system的情况
k = -1;
for (int i = 0; i < downSystem.size(); i++) {
if (arr[downSystem.get(i)] < arr[cur]) {
k = i;
break;
}
}
//搜放在up system的情况
if (k == -1) {
downSystem.add(cur);
dfs(total, upNumber, downNumber + 1, cur + 1);
downSystem.remove(downSystem.size() - 1);
}else {
int temp = downSystem.get(k);
downSystem.set(k, cur);
dfs(total, upNumber, downNumber, cur + 1);
downSystem.set(k, temp);
}
}
public static void main(String[] args) {
int n;
while ((n = in.nextInt()) != 0) {
arr = new int[n];
in.nextIntegerArray(arr);
res = Integer.MAX_VALUE;
dfs(n, 0, 0, 0);
out.println(res);
}
out.flush();
out.close();
}
AcWing 272. 最长公共上升子序列 原题链接
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。
小沐沐说，对于两个数列A和B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
数列A和B的长度均不超过3000。
输入格式
第一行包含一个整数N，表示数列A，B的长度。
第二行包含N个整数，表示数列A。
第三行包含N个整数，表示数列B。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
1≤N≤30001≤N≤3000,序列中的数字均不超过231−1231−1
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2
题目思路
朴素写法：
public static void main(String[] args) {
int n = in.nextInt();
int[] a = new int[n + 1];
int[] b = new int[n + 1];
int[][] dp = new int[n + 1][n + 1];
for (int i = 1; i < n + 1; i++) a[i] = in.nextInt();
for (int i = 1; i < n + 1; i++) b[i] = in.nextInt();
int res = 0;
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < n + 1; j++) {
dp[i][j] = dp[i - 1][j];
if (a[i] == b[j]) {
dp[i][j] = Math.max(dp[i][j], 1);
for (int k = 1; k < j; k++) {
if (b[k] < b[j])
dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + 1);
}
}
res = Math.max(res, dp[i][j]);
}
}
out.println(res);
out.flush();
out.close();
}
优化写法：
private static int functino2() {
int n = in.nextInt();
int[] a = new int[n + 1];
int[] b = new int[n + 1];
int[][] dp = new int[n + 1][n + 1];
for (int i = 1; i < n + 1; i++) a[i] = in.nextInt();
for (int i = 1; i < n + 1; i++) b[i] = in.nextInt();
int res = 0;
int max;
for (int i = 1; i < n + 1; i++) {
max = 0;
for (int j = 1; j < n + 1; j++) {
dp[i][j] = dp[i - 1][j];
if (a[i] == b[j]) dp[i][j] = Math.max(dp[i][j], max + 1);
if (a[i] > b[j]) max = Math.max(max, dp[i - 1][j]);
res = Math.max(res, dp[i][j]);
}
}
return res;
}