分析
设 \(f[i][j][k]\) 为当前考虑到第 \(i\) 个数有 \(j\) 个 \(p\) 和 \(k\) 个 \(q\)没有匹配的最大价值
转移的时候分两种情况
\(1\)、\(j\) 或 \(k\) 为 \(0\) ,此时 \(j\) 或 \(k\) 要枚举到序列能产生的最大贡献
\(2\)、\(j\) 和 \(k\) 都不为 \(0\),此时两重循环只要分别枚举到 \(40\) 即可
因为如果我们加入的数能够把 \(j\) 和 \(k\) 都消掉，那么因为这个数不会超过 \(2000\)，而 \(p\) 和 \(q\) 不会小于 \(50\)，所以新的贡献不会超过 \(40\)
如果都不会消掉，同上
如果只能消掉一个，必定有一维变成了 \(0\),有回到了第一种情况
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define rg register
const int maxn=55,maxm=2e3+5;
int a[maxn],p,q,n,f[3][maxm][maxm],ans,now;
void dp(int i,int j,int k){
for(rg int x=0;x*p<=a[i];x++){
rg int y=(a[i]-x*p)/q;
if(x<=k && y<=j){
f[now][j-y][k-x]=std::max(f[now][j-y][k-x],f[now^1][j][k]+x+y);
} else if(x<=k){
f[now][0][k-x+y-j]=std::max(f[now][0][k-x+y-j],f[now^1][j][k]+x+j);
} else if(y<=j){
f[now][x-k+j-y][0]=std::max(f[now][x-k+j-y][0],f[now^1][j][k]+k+y);
} else {
f[now][x-k][y-j]=std::max(f[now][x-k][y-j],f[now^1][j][k]+j+k);
}
}
}
int main(){
memset(f,0xcf,sizeof(f));
scanf("%d",&n);
for(rg int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d%d",&p,&q);
f[0][0][0]=0;
for(rg int i=1;i<=n;i++){
now^=1;
for(rg int j=0;j<=2000;j++){
f[now][j][0]=f[now][0][j]=0xcfcfcfcf;
}
for(rg int j=1;j<=40;j++){
for(rg int k=1;k<=40;k++){
f[now][j][k]=0xcfcfcfcf;
}
}
for(rg int j=0;j<=2000;j++){
dp(i,j,0);
dp(i,0,j);
}
for(rg int j=1;j<=40;j++){
for(rg int k=1;k<=40;k++){
dp(i,j,k);
}
}
}
for(rg int i=0;i<=2000;i++){
for(rg int j=0;j<=2000;j++){
ans=std::max(ans,f[now][i][j]);
}
}
printf("%d\n",ans*(p+q));
return 0;
}
