AcWing 1022. java
原题链接
简单
作者:
季之秋
,
2021-04-12 17:44:01
,
所有人可见
,
阅读 271
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m1 = sc.nextInt();
int m2 = sc.nextInt();
int n = sc.nextInt();
int f[][] = new int[1010][1010];
for(int i = 0; i < n; i ++){
int v1 = sc.nextInt();
int v2 = sc.nextInt();
for(int j = m1; j >= v1; j --){
for(int k = m2 - 1; k >= v2; k --) // 体力不超过m2-1的最大数量
f[j][k] = Math.max(f[j][k], f[j-v1][k-v2] + 1);
}
}
int k = m2 - 1;
while(k > 0 && f[m1][k - 1] == f[m1][m2 - 1]) k --; // 最终退回到等于数量相同且消耗体力最小的位置
System.out.println(f[m1][m2 - 1] + " " + (m2 - k) ); // m2是体力,k是消耗的体力
// f[m1][m2-1] 表示精灵球不超过m1个且总体力<m2的最大捕捉数量
}
}import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m1 = sc.nextInt();
int m2 = sc.nextInt();
int n = sc.nextInt();
int f[][] = new int[1010][1010];
for(int i = 0; i < n; i ++){
int v1 = sc.nextInt();
int v2 = sc.nextInt();
for(int j = m1; j >= v1; j --){
for(int k = m2 - 1; k >= v2; k --) // 体力不超过m2-1的最大数量
f[j][k] = Math.max(f[j][k], f[j-v1][k-v2] + 1);
}
}
int k = m2 - 1;
while(k > 0 && f[m1][k - 1] == f[m1][m2 - 1]) k --; // 最终退回到等于数量相同且消耗体力最小的位置
System.out.println(f[m1][m2 - 1] + " " + (m2 - k) ); // m2是体力,k是消耗的体力
// f[m1][m2-1] 表示精灵球不超过m1个且总体力<m2的最大捕捉数量
}
}