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

Download