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