CATGO - Cắt gỗ
Tác giả: ll931110
Ngôn ngữ: C++
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;
int n,m;
int g[52][52],f[52][502];
int a[52],len[52],val[52];
int main()
{
// freopen("catgo.in","r",stdin);
// freopen("catgo.ou","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 0; i < m; i++) scanf("%d %d", &len[i], &val[i]);
memset(g,0,sizeof(g));
for (int i = 0; i < m; i++) g[len[i]][0] = max(g[len[i]][0],val[i]);
for (int j = 1; j < 50; j++)
for (int i = 1; i <= 50; i++)
for (int t = 0; t < m; t++) if (i >= len[t]) g[i][j] = max(g[i][j],g[i - len[t]][j - 1] + val[t]);
memset(f,0,sizeof(f));
for (int i = 1; i <= n; i++)
for (int j = 0; j <= 500; j++)
for (int t = 0; t < a[i] && t <= j; t++) f[i][j] = max(f[i][j],f[i - 1][j - t] + g[a[i]][t]);
int best = 0;
for (int i = 0; i <= 500; i++) best = max(best,f[n][i] - i * (i + 1) / 2);
printf("%d\n", best);
};