Market
原题：（权限限制没有链接）
题目描述
在比特镇一共有n 家商店，编号依次为1 到n。每家商店只会卖一种物品，其中第i 家商店的物品单价为ci，价值为vi，且该商店开张的时间为ti。
Byteasar 计划进行m 次购物，其中第i 次购物的时间为Ti，预算为Mi。每次购物的时候，Byteasar会在每家商店购买最多一件物品，当然他也可以选择什么都不买。如果购物的时间早于商店开张的时间，那么显然他无法在这家商店进行购物。
现在Byteasar 想知道，对于每个计划，他最多能购入总价值多少的物品。请写一个程序，帮助Byteasar 合理安排购物计划。
注意：每次所花金额不得超过预算，预算也不一定要花完，同时预算不能留给其它计划使用。
输入输出格式
输入格式：
第一行包含两个正整数n;m，表示商店的总数和计划购物的次数。
接下来n 行，每行三个正整数ci; vi; ti，分别表示每家商店的单价、价值以及开张时间。
接下来m 行，每行两个正整数Ti;Mi，分别表示每个购物计划的时间和预算。
输出格式：
输出m 行，每行一个整数，对于每个计划输出最大可能的价值和。
输入输出样例
输入样例#1：
5 2
5 5 4
1 3 1
3 4 3
6 2 2
4 3 2
3 8
5 9
输出样例#1：
10 12
说明
n,vi,ti,Ti<=300
m<=10^5
ci,Mi<=10^9
个人解法：
一个神奇的背包。
如果我们考虑Mi很小，我们尽可以当做一个背包来做：
（将商店视为物品，预算视为背包容量）
首先我们将询问与物品均按照时间顺序排序。之后对于顺序处理每一个询问，我们根据物品出现时间，加入当前可以加入的物品，并且加入时更新F数组即可。
现在由于预算很大，达到了10^9，所以普通的01背包显然不行。
然而考场上想到了可行性背包DP却打不出来
我们发现，事实上价值vi很小，每一个预算最多得到的价值最多是vi*n，也就是10^5的级别。所以我们考虑，用F[i]表示收获i的最少的花费。
设maxnum=vi*n
每加入一个物品，更新F[0..maxnum]，更新的方法类似，即F[i]=min(F[i],F[i-vi[i]]+ci[i])。初始状态F[0]=0，F[1..maxnum]=none。none为一个很大的数，保证不会用于更新，根据此题来看，大于Mi（最大的花费）且小于maxlongint/2（避免longint越界）即可。
考虑到可能会出现：F[i]>F[j]且i<j的情况，此时F[i]这个状态是可以被F[j]替代的。所以可以用F[j]替代F[i]。
也就是：
for j:=maxnum downto vi[now] do
F[j]:=min(F[j],F[j-vi[now]]+ci[now]);
for j:=maxnum downto 1 do
F[j]:=min(F[j],F[j+1]);
这样我们保证了一个每一个F[i]储存的都是其最优答案。而且，F数组是一个不递减数组。
这样一来，我们就可以直接在数组中二分查找——查找F[i]<=Budget的最大的i，就是此次询问的最大价值。
这个算法复杂度是O(n*maxnum)=O(vi*n^2)=O(300^3)，比起某O(nm)=O(10^12)还是要好一些的。
代码如下：
type
inf=record
time,Budget,Identifier:longint;
end;
var
n,m,i,j,now,tl,tr,mid,maxnum:longint;
vi,ci,ti,F,Ans:array[0..100000] of longint;
Que:array[0..100000] of inf;
procedure swap(var a,b:longint);//排序
function min(a,b:longint):longint;//取较小值
procedure StoreSort(l,r:longint);//对物品按照时间顺序排序
procedure QueSort(l,r:longint);//对询问按照时间顺序排序
begin
read(n,m);//读入
randomize;
for i:=1 to n do
read(ci[i],vi[i],ti[i]);
StoreSort(1,n);//排序
maxnum:=n*300;
for i:=1 to m do
begin
read(Que[i].time,Que[i].Budget);//读入
Que[i].Identifier:=Que[i-1].Identifier+1;//记录编号
end;
QueSort(1,m);//排序
now:=1;
fillchar(F,sizeof(F),60);//初始化
F[0]:=0;
for i:=1 to m do//处理询问
begin
while (ti[now]<=Que[i].time) and (now<=n) do//加入可以加入的物品
begin
for j:=maxnum downto vi[now] do
F[j]:=min(F[j],F[j-vi[now]]+ci[now]);//更新DP数组
for j:=maxnum downto 1 do
F[j]:=min(F[j],F[j+1]);
inc(now);
end;
tl:=0;
tr:=maxnum;//二分查找，左边界应该为0
while tl<tr do
begin
mid:=(tl+tr) shr 1+1;
if F[mid]<=Que[i].Budget then tl:=mid
else tr:=mid-1;
end;
Ans[Que[i].Identifier]:=tl;//记录答案
end;
for i:=1 to m do
writeln(ans[i]);//输出
end.