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;
	}
}

Download