CATGO - Cắt gỗ

Tác giả: khuc_tuan

Ngôn ngữ: Java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; ++i)
			a[i] = sc.nextInt();
		int m = sc.nextInt();
		int[] v = new int[55];
		for (int i = 0; i < m; ++i) {
			int x = sc.nextInt();
			v[x] = sc.nextInt();
		}
		int[][] f = new int[55][55];
		for (int i = 0; i < f.length; ++i)
			for (int j = 0; j < f[i].length; ++j)
				if (j == 0)
					f[i][j] = v[i];
				else
					for (int len = 1; len < i; ++len)
						f[i][j] = Math.max(f[i][j], f[i - len][j - 1] + v[len]);
		int[][] g = new int[n][1000];
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < g[i].length; ++j)
				for (int t = 0; t < 55 && t <= j; ++t)
					g[i][j] = Math.max(g[i][j], (i == 0 ? 0 : g[i - 1][j - t])
							+ f[a[i]][t]);
		int total = 0;
		int res = 0;
		for (int x = 0; x < 1000; ++x) {
			total += x;
			res = Math.max(res, g[n - 1][x] - total);
		}
		System.out.println(res);
	}
}

Download