[问题描述]
给定 n 个物品, 每个物品可以不选或选一个, 第 i 个物品的价格为 ci, 价值为 vi, 出现时间为 ti. 有 m 个询问, 每次询问在出现时间不超过 Ti 的所有物品中选若干件, 总花费不超过 Mi 的情况下, 被选择物品的价值和的最大值是多少.
[输入格式]
第一行输入 n,m.
接下来 n 行每行 3 个整数表示 ci,vi,ti.
接下来 m 行询问每行 2 个整数表示 ti,mi.
[输出格式]
输出 m 行, 每行一个整数表示第 i 个询问的答案.
[样例输入]
- 5 2
- 3 6 1
- 5 7 4
- 8 2 9
- 10 1 7
- 3 3 4
- 9 50
- 4 30
[样例输出]
19
16
[数据规模]
%30: n≤10,m≤20; ci,vi,ti≤20,Mi≤1000
%60: n≤100,m≤1000; ci,Mi≤100000,vi≤100,ti<=300
%100: n≤300,m≤100000; ci,Mi≤10^9,vi≤300,ti<=300
[分析] 另类背包 + 单调优化
先将物品时间升序排列, 首先想到 01 背包, 但 c 和 M 太大无法承受.
考虑到 vi 很小: 记 f[i,j] 为 1..i 件物品选出 j 的价值和的最小花费, O(N^3), 空间刚好足够.
对于一个询问的答案就是:
1, 算出在 Ti 时间内所能购买的物品范围 [1,x]
2, 答案就是满足 f[x,j]≤Mi 的最大 j
暴力处理询问的话依然会 TLE
于是二分:
记 g[x,j] 为 f[x,j...] 的最小值, 这样 g[x] 就是单调增的
答案就是满足 g[x,j]≤Mi 的最大 j
本人总结:
一般的背包我们求最大值所以我们的初值可以放心的设置为 0
因为即使不能恰好凑到那个数目
我们可以以非 0 的容量为起点恰好凑到这个数目
但是如果我们改变状态求达到某个价值的容量最小值
我们明显不能凑到的地方始终都会是最大值
显然我们要求到一个价值的容量最小值
其实也就包含了更大的价值的最小值
有可能这个价值不能被恰好凑到, 这就是取 min 的特点
但相对于能凑到更大的价值用更小的空间, 我们可以理解成抛弃掉这么多空间来更新
所以我们这种情况下一定用原来的方法更新完之后要从后往前取保证单调性
因为我们不能从比自己小的价值的最小容量转移过来, 所以只能从后面转移过来了
在这道题目里面我们求某价值的最小容量
我们在查询的之后最小容量相同的情况下我们会找到最大的价值, 所以不会漏解
也就是找到刚好凑到的价值
从后往前取 min 保证二分可以顺利进行, 这就是意义所在
- code:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define N 1000006
- using namespace std;
- struct node {
- long long c,v,t;
- } s[N];
- bool cmp(const node&a,const node&b) {
- return a.t<b.t;
- }
- long long Time[N],f[301][90002],maxVal;
- long long n,m;
- long long Find(long long Judge) {
- long long l=1,r=n,mid;
- while(l<=r) {
- mid=(l+r)>>1;
- if(Time[mid]<=Judge)l=mid+1;
- else r=mid-1;
- }
- return r;
- }
- long long Find(long long x,long long Judge) {
- long long l=0,r=maxVal,mid;
- while(l<=r) {
- mid=(l+r)>>1;
- if(f[x][mid]<=Judge)l=mid+1;
- else r=mid-1;
- }
- return r;
- }
- long long read(){
- long long x=0,f=1;
- char c=getchar();
- while(!isdigit(c)){
- if(c=='-')f=-1;
- c=getchar();
- }
- while(isdigit(c)){
- x=(x<<3)+(x<<1)+c-'0';
- c=getchar();
- }
- return x*f;
- }
- int main() {
- cin>>n>>m;
- for(long long i=1; i<=n; i++) {
- s[i].c=read(),s[i].v=read(),s[i].t=read();
- maxVal+=s[i].v;
- }
- sort(s+1,s+n+1,cmp);
- for(long long i=1; i<=n; i++)Time[i]=s[i].t;
- memset(f,0x3f3f3f3f,sizeof f);
- f[0][0]=0;
- for(long long i=1; i<=n; i++) {
- for(long long j=maxVal; j>=0; j--) {
- if(j>=s[i].v)f[i][j]=min(f[i-1][j],f[i-1][j-s[i].v]+s[i].c);
- else f[i][j]=f[i-1][j];
- }
- }
- for(long long i=1; i<=n; i++) {
- for(long long j=maxVal-1; j>=0; j--) {
- f[i][j]=min(f[i][j],f[i][j+1]);
- }
- }
- for(long long i=1; i<=m; i++) {
- long long T,M;
- T=read(),M=read();
- cout<<Find(Find(T),M)<<'\n';
- }
- return 0;
- }
- //bag
- over
来源: http://www.bubuko.com/infodetail-2836062.html