小挖的买花
题目背景
小挖喜欢买花，但是 ta 太懒了！所以这个任务全权交给了你。
题目描述
花店里只有 \(n\) 株花，每一株花都有三个属性：价格 \(cost_i\)、美丽度 \(be_i\)、新鲜程度 \(fr_i\)。
小挖每次都有不同的要求。准确来说，对于第 \(j\) 次买花，你手里的钱至多能买下总价为 \(c_j\) 的花。同时，小挖还要求购买花的新鲜程度总和大于等于 \(f_j\)。而小挖希望知道，在满足 ta 给出的条件后，购买花的美丽度总和的最大值是多少？
小挖一共要让你买 \(q\) 次花，你能否正确回答 ta 的问题呢？
询问显然彼此独立。
输入格式
第 \(1\) 行，共两个数 \(n,q\) 。
第 \(2\sim n+1\) 行，每行三个数 \(cost_i,fr_i,be_i\)，分别表示一株花的三个属性。
第 \(n+2\sim n+q+1\) 行，每行两个数 \(c_j,f_j\) ，表示每次买花时的要求。
输出格式
共 \(q\) 行，每行一个数，表示美丽度总和的最大值。
样例 #1
样例输入 #1
5 1
2 4 5
4 3 3
1 3 2
3 4 3
3 2 5
10 10
样例输出 #1
15
提示
对于 \(20\%\) 的数据，\(3\leq n,q\leq 16\)。
对于 \(40\%\) 的数据，\(3\leq n,q\leq 30,0\leq c_j,f_j\leq 50\)。
对于 \(60\%\) 的数据，\(3\leq n\leq 100,1\leq q\leq 5\times 10^4,0\leq cost_i,fr_i,c_j,f_j\leq 100\)。
对于另外 \(20\%\) 的数据，对于每次买花，都有 \(f_j=0\)。
对于 \(100\%\) 的数据，\(3\leq n\leq 500,\boldsymbol{1\leq q\leq 10^6},0\leq cost_i,fr_i,c_j,f_j\leq 500, 1\leq be_i \leq 10^6\)。
注意事项
- 要用\(\textrm{scanf,printf}\)否则会\(TLE\)
- 要更新\(m1,m2\)，不能直接开\(500\)否则会\(TLE\)
- 注意不用开\(long~long\)！！
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510,M = 1000010;
int n,m1,m2,q;
int cost[N],be[N],fr[N];
int f[N][N];
int c[M],fresh[M];
int main () {
scanf ("%d%d",&n,&q);
for (int i = 1;i <= n;i++) scanf ("%d%d%d",&cost[i],&fr[i],&be[i]);
for (int i = 1;i <= q;i++) {
scanf ("%d%d",&c[i],&fresh[i]);
m1 = max (m1,c[i]);
m2 = max (m2,fresh[i]);
}
for (int i = 1;i <= n;i++) {
for (int j = m1;j >= cost[i];j--) {
for (int k = m2;k >= 0;k--) {
if (k <= fr[i]) f[j][k] = max (f[j][k],f[j - cost[i]][0] + be[i]);
else if (f[j - cost[i]][k - fr[i]]) f[j][k] = max (f[j][k],f[j - cost[i]][k - fr[i]] + be[i]);
}
}
}
for (int i = 1;i <= q;i++) printf ("%d\n",f[c[i]][fresh[i]]);
return 0;
}