CATGO - Cắt gỗ
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
using namespace std;
int value[51],a[51],n,g[51][51],f[51][101],ans;
int main()
{
int x,y,m;
cin >> n;
for (int i=1;i<=n;i++) cin >> a[i];
cin >> m;
while (m--) cin >> x >> y, value[x]=max(value[x],y);
// precalc for each bar
for (int i=1;i<=50;i++) g[i][0]=-1000000;
for (int i=1;i<=50;i++)
for (int j=1;j<=i;j++)
for (int ii=0;ii<i;ii++)
g[i][j]=max(g[i][j],g[ii][j-1]+value[i-ii]);
// dp
for (int i=1;i<=n;i++)
for (int j=1;j<=a[i];j++)
for (int k=j-1;k<=100;k++)
f[i][k]=max(f[i][k],f[i-1][k-j+1]+g[a[i]][j]);
for (int k=0;k<=100;k++) ans=max(ans,f[n][k]-k*(k+1)/2);
cout << ans << endl;
}