Input file: market.in
Output file: market.out
Time limit: 1 seconds
Memory limit: 128 megabytes
在比特镇一共有 n 家商店，编号依次为 1 到 n。每家商店只会卖一种物品，其中第 i 家商店的物品单价为 ci，价值为 vi，且该商店开张的时间为 ti。
Byteasar 计划进行 m 次购物，其中第 i 次购物的时间为 Ti，预算为 Mi。每次购物的时候， Byteasar会在每家商店购买最多一件物品，当然他也可以选择什么都不买。如果购物的时间早于商店开张的时间，那么显然他无法在这家商店进行购物。现在 Byteasar 想知道，对于每个计划，他最多能购入总价值多少的物品。请写一个程序，帮助Byteasar 合理安排购物计划。
注意：每次所花金额不得超过预算，预算也不一定要花完，同时预算不能留给其它计划使用。
Input
第一行包含两个正整数 n; m，表示商店的总数和计划购物的次数。
接下来 n 行，每行三个正整数 ci; vi; ti，分别表示每家商店的单价、价值以及开张时间。
接下来 m 行，每行两个正整数 Ti; Mi，分别表示每个购物计划的时间和预算。
Output
输出 m 行，每行一个整数，对于每个计划输出最大可能的价值和。
Examples
| market.in | market.out |
| 5 2 5 5 4 1 3 1 3 4 3 6 2 2 4 3 2 3 8 5 9 |
10 12 |
第一个计划可以在商店 2,3,5 各购买一件物品，总花费为 1 + 3 + 4 = 8，总价值为 3 + 4 + 3 = 10。
第二个计划可以在商店 1,2,3 各购买一件物品，总花费为 5 + 1 + 3 = 9，总价值为 5 + 3 + 4 = 12。
Notes
对于 100% 的数据， 1 ≤ ti; Ti ≤ n。
| 测试点编号 | n | m | ci; Mi | vi | ti; Ti |
| 1 | = 10 | = 5 | ≤ 10 | ≤ 10 | ≤ 10 |
| 2 | = 20 | = 10 | ≤ 100 | ≤ 100 | ≤ 20 |
| 3 | = 100 | = 1 | ≤ 100 | ≤ 100 | = 1 |
| 4 | = 200 | = 1 | ≤ 200 | ≤ 200 | = 1 |
| 5 | = 150 | = 100000 | ≤ 150 | ≤ 150 | ≤ 150 |
| 6 | = 300 | = 100000 | ≤ 300 | ≤ 300 | ≤ 300 |
| 7 | = 20 | = 100000 | ≤ 109 | ≤ 300 | ≤ 20 |
| 8 | = 200 | = 100000 | ≤ 109 | ≤ 200 | ≤ 200 |
| 9 | = 300 | = 100000 | ≤ 109 | ≤ 300 | ≤ 300 |
| 10 | = 300 | = 100000 | ≤ 109 | ≤ 300 | ≤ 300 |
分析
这很显然是一个背包问题，前60分是很好写的，但是后面的背包容量就有点大了，我们开不了这么大的数组，但仔细观察数据你会发现vi是很小的，所以用二分+动态规划就行了。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=300+5; const int maxm=100000+5; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int n,m,now,tail,lim; int ans[maxm],q[maxm],f[maxn*maxn]; struct node{int c,v,t;}a[maxn]; struct data{int t,m,id;}b[maxm]; bool cmp1(node x,node y){return x.t<y.t;} bool cmp2(data x,data y){return x.t<y.t;} inline void add(int v,int c) { for(int i=lim;i>=v;i--) f[i]=min(f[i],f[i-v]+c); for(int i=lim-1;i>=0;i--) f[i]=min(f[i],f[i+1]); } inline int query(int x) { int l=0,r=lim,ans; while(l<=r) { int mid=(l+r)>>1; if(f[mid]<=x) {ans=mid; l=mid+1;} else r=mid-1; } return ans; } int main() { freopen("market.in","r",stdin); freopen("market.out","w",stdout); n=read();m=read(); lim=n*301; for(int i=1;i<=n;i++) a[i].c=read(),a[i].v=read(),a[i].t=read(); for(int i=1;i<=m;i++) b[i].t=read(),b[i].m=read(),b[i].id=i; sort(a+1,a+n+1,cmp1); sort(b+1,b+m+1,cmp2); memset(f,0x3f,sizeof(f)); f[0]=0; for(int i=1;i<=m;i++) { now=tail+1; if(now<=n) for(int j=now;j<=n;j++) if(b[i].t>=a[j].t) {add(a[j].v,a[j].c); tail++;} else break; ans[b[i].id]=query(b[i].m); } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }