CATGO - Cắt gỗ
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 53;
const int lim = 73;
using namespace std;
int F[N][N][lim];
int res, n, m;
int a[N], val[N];
void maximize(int &a, int b)
{a = a > b ? a : b; res = res > a ? res : a;}
int main() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
cin >> m;
int d, v;
for(int i = 1; i <= m; i++) {
cin >> d >> v;
val[d] = v;
}
memset(F, 255, sizeof F);
F[1][a[1]][0] = 0;
for(int i = 1; i <= n; i++)
for(int j = a[i]; j; j--)
for(int k = 0; k < lim - 1; k++)
if (F[i][j][k] != -1) {
for(int t = 1; t < j; t++)
maximize(F[i][j - t][k + 1], F[i][j][k] + val[t] - k - 1);
maximize(F[i + 1][a[i + 1]][k], F[i][j][k] + val[j]);
}
cout << res;
return 0;
}