题目大意：
给定(n)个物品，有价格、价值、可购买时间三个属性，给定(m)个查询，有购买时间、预算两个属性。显然的是只有当购买的时间大于一个物品的可购买时间时，这个物品才可以买。求每次查询能买到最大价值。
输入样例
5 2
5 5 4
1 3 1
3 4 3
6 2 2
4 3 2
3 8
5 9
输出样例
10
12
数据范围
反思
想来想去，还是写一下这道很搞我心态的题。考试的时候20min砍掉T1，30min上对拍，然后将近2h全扔在这道题上了。主要是写着写着就好像上头了，总觉得这么简单的题说什么也要A了它，但是无论怎样都是感觉跟“正解”差一点点(然而下来发现正解的复杂度就是很迷)，然后就一直死磕，最后发现暴力是挂的，爆了零。而且后面两道题也都没留时间，T4 10min打了个60分暴力结果最裸的30分挂了，T3 干脆连暴力都没打完。
感觉都这时候了还犯这种决策性失误有点说不过去，而且连暴力都打挂是更说不过去的...可能也跟昨天两次考试全部原地爆炸的梦幻开局有关系吧，心态太浮躁，太急功近利了。
还是稳一点吧，就我这种水平也不求翻盘了(已经被甩了300分了还翻个P)，至少后面的考试别再挂分了，把能拿的分都拿到也就是成功了。
题解
就一道挺傻的背包...价格很大但价值很小，于是转换一下维度，挺套路的。然后问题是询问很多，很恶心。发现其实时间的范围很小，所以应该挺容易就能想到按时间把答案预处理出来，这应该也挺套路的。至于查询的预算不一样怎么办，我们可以手动把dp数组弄成单调的，原理就是如果价值更多的方案价格反而要少，就用他去覆盖那些价值少价格高的。这也是正解的思路。但问题是如果刻意构造数据把所有物品的可购买时间都放到一天，预处理2e7的复杂度就会直接乘上300，这也是让我纠结了半天的点。最终还是没写这个，脑子一抽写了个时间复杂度是对的，但会炸内存而且实际上写错了的做法...
放一下考场的0分代码，提醒一下自己吧。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
inline int read() {
int s = 0;
char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
return s;
}
const int maxn = 1e5 + 10;
struct node {
int c, val, t;
}shop[302];
bool cmp(node a, node b) { return a.t < b.t; }
int n, m;
int sum[302];
struct DP {
int w, id;
}dp[302][40002];
bool cmp2(DP a, DP b) { return a.w < b.w; }
int main() {
freopen("market.in", "r", stdin);
freopen("market.out", "w", stdout);
n = read(), m = read();
for (int i = 1; i <= n; i++) {
shop[i].c = read();
shop[i].val = read();
shop[i].t = read();
sum[i] = sum[i - 1] + shop[i].val;
}
sort(shop + 1, shop + 1 + n, cmp);
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i <= n; i++) dp[i][0].w = 0;
for (int q = 1; q <= n; q++) {
for (int j = sum[q]; j >= shop[q].val; j--) {
dp[q][j].id = j;
dp[q][j].w = min(min(dp[q][j].w, dp[q - 1][j].w), dp[q - 1][j - shop[q].val].w + shop[q].c);
}
for (int j = shop[q].val - 1; j >= 0; j--) dp[q][j].id = j, dp[q][j].w = dp[q - 1][j].w;
}
for (int q = 1; q <= n; q++) {
sort(dp[q], dp[q] + 1 + sum[q], cmp2);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum[i]; j++) {
if (j) dp[i][j].id = max(dp[i][j].id, dp[i][j - 1].id);
}
}
int T, M;
while (m--) {
T = read(), M = read();
int l = 1, r = n, mid, id;
while (l <= r) {
mid = (l + r) >> 1;
if (shop[mid].t < T) l = mid + 1;
else r = mid - 1;
}
if (l > n) l = n;
id = l;
l = 0, r = sum[id];
while (l <= r) {
mid = (l + r) >> 1;
if (dp[id][mid].w < M) l = mid + 1;
else r = mid - 1;
}
//printf("l = %d r = %d
", l, r);
printf("%d
", dp[id][l].id);
}
return 0;
}
AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 305;
struct node {
int c, v;
};
int n, m;
int dp[305][90001];
vector<node> tim[305];
int main() {
//freopen("market.in", "r", stdin);
//freopen("market.out", "w", stdout);
scanf("%d %d", &n, &m);
int c, v, t;
for (int i = 1; i <= n; i++) {
scanf("%d %d %d", &c, &v, &t);
tim[t].push_back((node) { c, v });
}
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for (int t = 1; t <= 300; t++) {
for (int i = 0; i <= n * 300; i++) dp[t][i] = dp[t - 1][i];
for (int i = 0; i < tim[t].size(); i++) {
int c = tim[t][i].c, v = tim[t][i].v;
for (int j = n * 300; j >= v; j--) dp[t][j] = min(dp[t][j], dp[t][j - v] + c);
}
for (int i = n * 300 - 1; i >= 0; i--) dp[t][i] = min(dp[t][i], dp[t][i + 1]); //如果i更大，而所需价格更少
}
int T, M;
while (m--) {
scanf("%d %d", &T, &M);
int l = 0, r = n * 300, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (dp[T][mid] <= M) l = mid + 1;
else r = mid - 1;
}
//for (int i = 1; i <= 20; i++) printf("dp[%d][%d] = %d
", T, i, dp[T][i]);
printf("%d
", l - 1);
}
}