1674

WillFan
zhou_小生

losabsolutely
Puff_3
crFlowerz
krio
ashionial
TheC

3天前
import java.util.*;
public class Main{

static int N = 1010;
static int f[] = new int[N];
static int l[] = new int[N], h[] = new int[N], v[] = new int[N], w[] = new int[N];
static int n, m, v0, w0;

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
v0 = sc.nextInt();
w0 = sc.nextInt();

// 第0个物品在满足体积要求的情况下可以装无数个，是完全背包问题
for(int i = v0; i <= m; i++) f[i] = Math.max(f[i], f[i - v0] + w0);

for(int i = 1; i <= n; i++){
l[i] = sc.nextInt();
h[i] = sc.nextInt();
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}

// 后面的n个物品是多重背包问题，每个物品最多可以选 l/h 个
for(int i = 1; i <= n; i++){
for(int j = m; j > 0; j--){
for(int k = 0; k <= l[i] / h[i] && k * v[i] <= j; k++){
f[j] = Math.max(f[j], f[j - k * v[i]] + k * w[i]);
}
}
}
System.out.println(f[m]);
sc.close();
}
}

4天前
import java.io.*;
import java.util.*;

public class Main {

static int N = 510, M = 6010;
static int f[][] = new int[N][M];
static int v[] = new int[N], w[] = new int[N], s[] = new int[N];
static int n, m;

public static void main(String[] args) throws IOException {
StreamTokenizer stmInput = new StreamTokenizer(br);
stmInput.nextToken();
n = (int)stmInput.nval;
stmInput.nextToken();
m = (int)stmInput.nval;
for(int i = 1; i <= n; i++){
stmInput.nextToken();
v[i] = (int)stmInput.nval;
stmInput.nextToken();
w[i] = (int)stmInput.nval;
stmInput.nextToken();
s[i] = (int)stmInput.nval;
}

for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
for(int k = 0; k <= s[i] && k * v[i] <= j; k++){
f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
System.out.println(f[n][m]);
br.close();
}
}

4天前
// f[i][j]: 在前i个数中选且总和恰好为j的所有选法的集合
// 属性: 所有选法的数量cnt
import java.util.*;
public class Main{

static int N = 10010;
static int f[] = new int[N];
static int v[] = new int[N];
static int n, m;

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i = 1; i <= n; i++){
v[i] = sc.nextInt();
}
// f[0][0] = 1; f[0][j] = 0
f[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
f[j] += f[j - v[i]];
}
}
System.out.println(f[m]);
sc.close();
}

}

4天前
import java.io.*;
import java.util.*;

public class Main {

static int N = 22, M = 80, INF = (int)1e9;
static int f[][] = new int[N][M];
static int n, m, k;

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StreamTokenizer stmInput = new StreamTokenizer(br);
stmInput.nextToken();
n = (int)stmInput.nval;
stmInput.nextToken();
m = (int)stmInput.nval;
stmInput.nextToken();
k = (int)stmInput.nval;

for(int i = 0; i < N; i++) Arrays.fill(f[i], INF);
f[0][0] = 0; // 一个都不选的重量为0

// 在前i个物品中选且总v1至少为j，总v2至少为k的所有选法的集合
// 最小重量
while(k-- != 0){
stmInput.nextToken();
int v1 = (int)stmInput.nval;
stmInput.nextToken();
int v2 = (int)stmInput.nval;
stmInput.nextToken();
int w = (int)stmInput.nval;
for(int j = n; j >= 0; j--){
for(int k = m; k >= 0; k--){
f[j][k] = Math.min(f[j][k], f[Math.max(0, j - v1)][Math.max(0, k - v2)] + w);
}
}
}
System.out.println(f[n][m]);
bw.flush();
bw.close();
br.close();
}
}

4天前
import java.io.*;
import java.util.*;

public class Main {

static int N = 1010, G = 110;
static int f[][] = new int[G][G];
static int v[] = new int[N], m[] = new int[N], w[] = new int[N];
static int n, V, M;

public static void main(String[] args) throws IOException {
StreamTokenizer stmInput = new StreamTokenizer(br);
stmInput.nextToken();
n = (int)stmInput.nval;
stmInput.nextToken();
V = (int)stmInput.nval;
stmInput.nextToken();
M = (int)stmInput.nval;
for(int i = 1; i <= n; i++){
stmInput.nextToken();
v[i] = (int)stmInput.nval;
stmInput.nextToken();
m[i] = (int)stmInput.nval;
stmInput.nextToken();
w[i] = (int)stmInput.nval;
}

for(int i = 1; i <= n; i++){
for(int j = V; j >= v[i]; j--){
for(int k = M; k >= m[i]; k--){
f[j][k] = Math.max(f[j][k], f[j - v[i]][k - m[i]] + w[i]);
}
}
}
System.out.println(f[V][M]);
br.close();
}
}

4天前
import java.io.*;
import java.util.*;

public class Main {

static int N = 1010, M = 510;
static int f[][] = new int[N][M];
static int v1[] = new int[N], v2[] = new int[M];
static int n, V1, V2;

public static void main(String[] args) throws IOException {
StreamTokenizer stmInput = new StreamTokenizer(br);
stmInput.nextToken();
V1 = (int)stmInput.nval;
stmInput.nextToken();
V2 = (int)stmInput.nval;
stmInput.nextToken();
n = (int)stmInput.nval;
for(int i = 1; i <= n; i++){
stmInput.nextToken();
v1[i] = (int)stmInput.nval;
stmInput.nextToken();
v2[i] = (int)stmInput.nval;
}

// 二维费用的背包问题
for(int i = 1; i <= n; i++){
for(int j = V1; j >= v1[i]; j--){
// 皮卡丘的体力值不能减少为0，所以k从V2-1开始
for(int k = V2 - 1; k >= v2[i]; k--){
f[j][k] = Math.max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
}
}
}
System.out.print(f[V1][V2 - 1] + " ");

// 在能收服的小精灵最多的情况下，小精灵的体力值之和最少是多少？
// 也就能求出皮卡丘所剩体力值的最大值。
int k = V2 - 1; // k为小精灵体力值之和，最大为V2-1
while(k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k--;
System.out.print(V2 - k);

br.close();
}
}

5天前
import java.util.*;
public class Main{

static int N = 35, M = 20010;
static int f[] = new int[N * M];
static int v[] = new int[N];
static int n, m;

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
for(int i = 1; i <= n; i++){
v[i] = sc.nextInt();
}

for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
f[j] = Math.max(f[j], f[j - v[i]] + v[i]);
}
}
System.out.println(m - f[m]);
sc.close();
}
}

5天前
import java.util.*;
public class Main{

static int N = 1010;
static int f[] = new int[N];
static int v[] = new int[N], w[] = new int[N];
static int n, m;

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
m = sc.nextInt();
n = sc.nextInt();
for(int i = 1; i <= n; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}

for(int i = 1; i <= n; i++){
for(int j = m; j >= v[i]; j--){
f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
}
}
System.out.println(f[m]);
sc.close();
}
}

5天前
import java.io.*;
import java.util.*;

public class Main {

static class Cow{
int w, s;
public Cow(int w, int s){
this.w = w;
this.s = s;
}
}
static int N = 50010;
static Cow cows[] = new Cow[N];
static int n;

public static void main(String[] args) throws IOException {
StreamTokenizer stmInput = new StreamTokenizer(br);
stmInput.nextToken();
n = (int)stmInput.nval;
for(int i = 0; i < n; i++){
stmInput.nextToken();
int w = (int)stmInput.nval;
stmInput.nextToken();
int s = (int)stmInput.nval;
cows[i] = new Cow(w, s);
}
// 按w+s从小到大排序
Arrays.sort(cows, 0, n, (a, b) -> {return a.w + a.s - b.w - b.s;});
// 计算最大危险值
long res = (long)-2e9, sum = 0;
for(int i = 0; i < n; i++){
res = Math.max(res, sum - cows[i].s);
sum += cows[i].w;
}
System.out.println(res);
br.close();
}
}

5天前
import java.io.*;
import java.util.*;

public class Main {

static int N = 100010;
static int a[] = new int[N];
static int n;

public static void main(String[] args) throws IOException {
StreamTokenizer stmInput = new StreamTokenizer(br);
stmInput.nextToken();
n = (int)stmInput.nval;
for(int i = 0; i < n; i++){
stmInput.nextToken();
a[i] = (int)stmInput.nval;
}
Arrays.sort(a, 0, n);

long res = 0;
for(int i = 0; i < n; i++) res += Math.abs(a[i] - a[n / 2]);
System.out.println(res);
br.close();
}
}