private static class Pet {
private int number;
private int power;
public Pet(int number, int power) {
this.number = number;
this.power = power;
}
}
public static void main(String[] args) {
int number = in.nextInt();
int power = in.nextInt();
int n = in.nextInt();
Pet[] pets = new Pet[n + 1];
int[][] dp = new int[number + 1][power + 1];
for (int i = 1; i < n + 1; i++) pets[i] = new Pet(in.nextInt(), in.nextInt());
for (int i = 1; i < n + 1; i++) {
for (int j = number; j >= pets[i].number; j--) {
for (int k = power - 1; k >= pets[i].power; k--) {
dp[j][k] = Math.max(dp[j][k], dp[j - pets[i].number][k - pets[i].power] + 1);
}
}
}
int num = dp[number][power - 1];
int res = power - 1;
for (int i = power - 1; i >= 0; i--) {
if (num == dp[number][i]) res = i;
else break;
}
out.println(num + " " + (power - res));
out.flush();
out.close();
}
活动打卡代码
AcWing 1022. 宠物小精灵之收服
活动打卡代码
AcWing 1024. 装箱问题
public static void main(String[] args) {
int m = in.nextInt();
int n = in.nextInt();
int[] arr = new int[n + 1];
int[] dp = new int[m + 1];
for (int i = 1; i < n + 1; i++) arr[i] = in.nextInt();
for (int i = 1; i < n + 1; i++) {
for (int j = m; j >= arr[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - arr[i]] + arr[i]);
}
}
out.println(m - dp[m]);
out.flush();
out.close();
}
活动打卡代码
AcWing 423. 采药
private static class Herb{
private int time;
private int value;
public Herb(int time, int value) {
this.time = time;
this.value = value;
}
}
public static void main(String[] args) {
// function1();
function2();
}
private static void function2() {
int t = in.nextInt();
int n = in.nextInt();
Herb[] herbs = new Herb[n + 1];
for (int i = 1; i <= n; i++) {
herbs[i] = new Herb(in.nextInt(), in.nextInt());
}
int[] dp = new int[t + 1];
for (int i = 1; i <= n; i++) {
for (int j = t; j >= herbs[i].time; j--) {
dp[j] = Math.max(dp[j], dp[j - herbs[i].time] + herbs[i].value);
}
}
out.println(dp[t]);
out.flush();
out.close();
}
活动打卡代码
AcWing 6. 多重背包问题 III
朴素写法：
private static void function1() {
int n = in.nextInt();
int m = in.nextInt();
Goods[] gs = new Goods[n + 1];
for (int i = 1; i < n + 1; i++) gs[i] = new Goods(in.nextInt(), in.nextInt(), in.nextInt());
int[][] dp = new int[n + 1][m + 1];
// int[][] last = new int[n + 1][m + 1];
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i < n + 1; i++) {
int v = gs[i].volume;
int w = gs[i].weight;
int number = gs[i].number;
//r : remainder
for (int r = 0; r < v; r++) {
list.clear();
for (int k = 0; r + k * v <= m; k++) {
if (!list.isEmpty() && k - list.getFirst() > number) list.removeFirst();
while (!list.isEmpty() &&
dp[i - 1][r + k * v] - k * w >=
dp[i - 1][r + list.getLast() * v] - list.getLast() * w
) {
list.removeLast();
}
list.add(k);
dp[i][r + k * v] = dp[i - 1][r + list.getFirst() * v] + ((k - list.getFirst()) * w);
}
}
}
out.println(dp[n][m]);
out.flush();
out.close();
}
空间优化写法：
private static void function2() {
int n = in.nextInt();
int m = in.nextInt();
Goods[] gs = new Goods[n + 1];
for (int i = 1; i < n + 1; i++) gs[i] = new Goods(in.nextInt(), in.nextInt(), in.nextInt());
int[] dp = new int[m + 1];
int[] bak = new int[m + 1];
// int[][] last = new int[n + 1][m + 1];
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i < n + 1; i++) {
System.arraycopy(dp, 0, bak, 0, m + 1);
int v = gs[i].volume;
int w = gs[i].weight;
int number = gs[i].number;
//r : remainder
for (int r = 0; r < v; r++) {
list.clear();
for (int k = 0; r + k * v <= m; k++) {
if (!list.isEmpty() && k - list.getFirst() > number) list.removeFirst();
while (!list.isEmpty() &&
bak[r + k * v] - k * w >=
bak[r + list.getLast() * v] - list.getLast() * w
) {
list.removeLast();
}
list.add(k);
dp[r + k * v] = bak[r + list.getFirst() * v] + ((k - list.getFirst()) * w);
}
}
}
out.println(dp[m]);
out.flush();
out.close();
}
活动打卡代码
AcWing 272. 最长公共上升子序列
题目思路
$$
f(i,j):所有由A串前i个元素和B串前j个元素且以b_j结尾元素组成的公共上升子序列的最大长度
$$
$$
集合按照是否包含a_i元素分为：
$$
$$
f(i-1,j):一定不包含a_i元素的公共上升子序列\tag1
$$
$$
一定包含a_i元素，因为是公共子序列所以一定需要满足a_i=b_j
$$
$$
max(f(i-1,k)+1)(1<=k<j\& b_k<a_i)\tag2
$$
$$
找到所有由A串前i-1个元素和B串前k个元素且以b_k结尾元素组成的公共上升子序列的最大长度,加上a_i,b_j这一对的长度
$$
$$
f(i,j)=max((1),(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();
}
优化写法：
$$
因为a_i=b_j,将其替换发现
$$
$$
每次循环求得的max是满足a_i > b_k的f(i - 1,k)的前缀最大值
$$
$$
因此可以直接将max提到第一层循环外面，减少重复计算，此时只剩下两重循环。
$$
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;
}
活动打卡代码
AcWing 187. 导弹防御系统
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);
}
k = -1;
for (int i = 0; i < downSystem.size(); i++) {
if (arr[downSystem.get(i)] < arr[cur]) {
k = i;
break;
}
}
//搜放在down 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);
}
}
活动打卡代码
AcWing 1016. 最大上升子序列和
public static void main(String[] args) {
int n = in.nextInt();
int[] arr = new int[n + 1];
int[] dp = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
arr[i] = in.nextInt();
}
int res = 0;
for (int i = 1; i < n + 1; i++) {
dp[i] = 1;
for (int j = 1; j < n + 1; j++) {
if (arr[j] < arr[i])
dp[i] = Math.max(dp[i], dp[j] + arr[i]);
}
res = Math.max(res, dp[i]);
}
out.println(res);
out.flush();
out.close();
}
活动打卡代码
AcWing 1012. 友好城市
private static class City{
private int a;
private int b;
public City(int a, int b) {
this.a = a;
this.b = b;
}
}
public static void main(String[] args) {
int n = in.nextInt();
int[] dp = new int[n + 1];
City[] cities = new City[n];
for (int i = 0; i < n; i++) {
cities[i] = new City(in.nextInt(), in.nextInt());
}
Arrays.sort(cities, Comparator.comparingInt(a -> a.a));
int res = 0;
for (int i = 1; i <= n; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (cities[j - 1].b < cities[i - 1].b) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
out.println(res);
out.flush();
out.close();
}
活动打卡代码
AcWing 1010. 拦截导弹
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 482. 合唱队形
public static void main(String[] args) {
int n = in.nextInt();
int[] arr = new int[n + 1];
int[] leftToRightDp = new int[n + 1];
int[] rightToLeftDp = new int[n + 1];
for (int i = 1; i <= n; i++) arr[i] = in.nextInt();
for (int i = 1; i <= n; i++) {
leftToRightDp[i] = 1;
for (int j = 1; j < i; j++) {
if (arr[j] < arr[i]) {
leftToRightDp[i] = Math.max(leftToRightDp[i], leftToRightDp[j] + 1);
}
}
}
for (int i = n; i >= 1; i--) {
rightToLeftDp[i] = 1;
for (int j = n; j > i; j--) {
if (arr[j] < arr[i]) {
rightToLeftDp[i] = Math.max(rightToLeftDp[i], rightToLeftDp[j] + 1);
}
}
}
int res = 0;
for (int i = 1; i < n + 1; i++) res = Math.max(res, leftToRightDp[i] + rightToLeftDp[i] - 1);
out.println(n - res);
out.flush();
out.close();
}
