分析
二维费用背包模板
AC代码
#include <bits/stdc++.h>
using namespace std;
const int Maxn=505;
int a[Maxn],b[Maxn],c[Maxn];
int f[Maxn][Maxn];
inline int read() {
int w=0,x=0; char ch=0;
while (!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return w?-x:x;
}
int Max(int n,int m) {return n>m?n:m;}
int main() {
int w=read(),m=read(),n=read();
for (int i=1;i<=n;i++) a[i]=read(),b[i]=read(),c[i]=read();
for (int i=1;i<=n;i++) {
for (int j=w;j>=a[i];j--) {
for (int k=m;k>=b[i];k--) {
f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+c[i]);
}
}
}
printf("%d
",f[w][m]);
return 0;
}