题目描述：
为了迎接节日，商店街策划了一次”火舞之人“促销大酬宾活动。每个在活动开始当天来商店街消费的客人，都可以在最多抽奖两次，根据抽到的卡片获得不同的优惠。已知卡池里面有红色的小绵羊卡、黑色的小鲨鱼卡、紫色的大尾巴狼卡以及一张看上去就很稀有的眯眯眼天使卡。然而你就比较厉害了，“啪”的一下抽出来一张不在卡池中的橙色小火龙卡。老板表示这是我们下一期活动的顶级卡，不知道怎么的就混进去了，作为补偿，他会向你透露下期活动的优惠内容，你可以提前开始准备参加下一期的促销活动。
在下一期活动中，共有N种商品会进行打折，第i种商品打折后的价格为Ci，原价为Vi，从第Ti天开始出售，每种商品限购一件。如果顾客来的时间早于第Ti天，就无法购买到这件商品。由于你工作很忙，周周007，自然不可能每天去超市。现在你想知道，倘若你只在第X天带了Y块钱去一次超市，最多可以购买到原价总和为多少的商品。
输入格式：
第一行包括两个正整数N，M，表示有N种商品进行促销，有M个购物询问。
接下来的N行，每行包括三个正整数Ci, Vi, Ti, 分别表示每种商品的折后价，原价， 和开放购买的日期。
接下来的M行，每行包括两个正整数Xi和Yi，表示你想知道第Xi天带着Yi去购物最多能买到原价总和多少的商品。
输出格式：
输出包括M行，每行一次整数，表示对应的购物计划所能买的最大原价总和。
样例输入：
5 2
5 5 4
1 3 1
3 4 3
6 2 2
4 3 2
3 8
5 9
样例输出：
10
12
HINT：
对于第一个计划，购买第2,3,5种商品收益最高。
对于第二个计划，购买第1,2,3种商品收益最高。
对于60%的测试数据, N<=200,M<=1000,Ci,Yi,Vi,Ti,Xi<=300。
对于100%的测试数据，
N<=300,M<=105,Ci,Yi<=109,Vi<=300,Ti,Xi<=300。
解法：
首先想到把物品按能购买的天数Ti进行排序，把M次询问转化为M次的0-1背包选择问题，结果存在数组里，最后一次性输出。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
struct rec { int w, v, d; }e[301];
struct node { int d, m, id; }q[100001];
int n, m;
int dp[100000];
int ans[100001];
bool cmp1(rec a, rec b) { return a.d < b.d; }
bool cmp2(node a, node b) { return a.d < b.d; }
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &e[i].w, &e[i].v, &e[i].d) ;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &q[i].d, &q[i].m);
q[i].id = i;
}
sort(e + 1, e + n + 1, cmp1);
sort(q + 1, q + m + 1, cmp2);
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
int j = 1;
for (int i = 1; i <= m; i++)
{
while (j <= n && e[j].d <= q[i].d)
{
for (int k = n * 300; k >= e[j].v; k--)
dp[k] = min(dp[k], dp[k - e[j].v] + e[j].w);
for (int k = n * 300; k; k--)
dp[k] = min(dp[k], dp[k + 1]);
j++;
}
ans[q[i].id] = upper_bound(dp + 1, dp + n * 300 + 1, q[i].m) - dp - 1;//把算出来的id值存在ans数组里面，因为我们只需要倒着找到最大的id值而已。
}
for (int i = 1; i <= m; i++)
cout << ans[i] << endl;
return 0;
}
众所周知，出题老师都是老阴比....
眼尖的同学一眼就在题目中发现了，Yi<=10^9，这么大的数字去做0-1背包选择，代码丢进去十有八九就当场去世了。
没错，这是一个大容量背包问题，思路是反过来，不找带Yi钱能买到的最大原价的东西，去找能达到最大原价某个值W下花最小的钱y，如果这个y小于Yi，则表示可以满足。
背包问题简单粗暴，“背包九讲”走一遍，一切都变得简单了。
最后
附上这次优秀作业的演示PPT
链接：https://pan.baidu.com/s/1I_mOKkFHj0Sw1gvLvkmPuA
提取码：869s
