TRIBE - Bộ lạc
Tác giả: khuc_tuan
Ngôn ngữ: Java
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
static class Word {
String w;
int na, nb;
int value;
}
static int n;
static int x, y, z;
static Word[] a;
static int[][][][] F;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
x = sc.nextInt();
y = sc.nextInt();
z = sc.nextInt();
sc.nextLine();
a = new Word[n];
for (int i = 0; i < n; ++i) {
String[] tmp = sc.nextLine().split(" ");
a[i] = new Word();
a[i].w = tmp[0];
a[i].value = Integer.parseInt(tmp[1]);
}
Arrays.sort(a, new Comparator<Word>() {
public int compare(Word w1, Word w2) {
return w1.w.compareTo(w2.w);
}
});
for (int i = 0; i < n; ++i)
for (int j = 0; j < a[i].w.length(); ++j)
if (a[i].w.charAt(j) == 'a')
++a[i].na;
else
++a[i].nb;
F = new int[x + 1][y + 1][z + 1][2];
for (int[][][] a3 : F)
for (int[][] a2 : a3)
for (int[] a1 : a2)
Arrays.fill(a1, -1);
System.out.println(truyvet(x, y, z, 0));
}
static String truyvet(int x, int y, int z, int need) {
int res = calc(x, y, z, need);
// if (z > 0 && res == calc(x, y, z - 1, 0))
// return " " + truyvet(x, y, z - 1, 0);
for (int k = 0; k < a.length; ++k) {
if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
if (res == now + a[k].value)
return (need == 0 ? "" : " ") + a[k].w
+ truyvet(x - a[k].na, y - a[k].nb, z - need, 1);
}
}
return "";
}
static int calc(int x, int y, int z, int need) {
if (F[x][y][z][need] != -1)
return F[x][y][z][need];
int res = 0;
// if (z > 0)
// res = Math.max(res, calc(x, y, z - 1, 0));
for (int k = 0; k < a.length; ++k)
if (a[k].na <= x && a[k].nb <= y && z - need >= 0) {
int now = calc(x - a[k].na, y - a[k].nb, z - need, 1);
res = Math.max(res, now + a[k].value);
}
return F[x][y][z][need] = res;
}
}