算法题

链接

题目大意：给定n个饭盒，和q次询问，每个饭盒拥有美味值v，代价w，取走时间e。每次询问包含一个时间t，和代价上限k。问再此时间，此代价下，能获得的最大美味值是多少？

背包问题，dp[i][j]表示当前可以取走i件物品，且代价为小于等于j可获得的最大值。那么在这问题里，最直接的方法就是选出符合条件的饭盒进行背包DP，但是这会超时。

其实我们只需要把饭盒按照取走时间降序排序，然后做一遍背包DP，这样dp数组的物品维度使按照取走顺序排列的。（dp[1]代表对最后被拿走的物品进行DP，dp[2]代表最后一个和倒数第二个被取走的物品进行DP，以此类推）然后用二分法确定DP[i][j]中的i（某时间段哪些饭盒可以进行DP）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;


int dp[10001][10001];
struct hehe{

  int v,w;
  long long e;
}a[10001];


bool cmp(hehe l,hehe r){
  return l.e>r.e;
}
int n,q;

int find(long long num){
  int l=1;
  int r=n;
  int mid;
  int ans=0;
  while(l<=r){
    mid=(l+r)/2;
    if(a[mid].e>num){
      ans=mid;
      l=mid+1;
    }
    else{
      r=mid-1;
    }
  }
  return ans;
}

int main(){
  scanf("%d%d",&n,&q);
  for(int i=1;i<=n;i++){
    scanf("%d%d%lld",&a[i].v,&a[i].w,&a[i].e);
  }
  sort(a+1,a+1+n,cmp);
  for(int i=1;i<=n;i++){
    for(int j=0;j<=10000;j++){
      dp[i][j]=dp[i-1][j];
      if(j>=a[i].w){
        dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].w]+a[i].v);
      }
    }
  }
  int t,k;
  for(int i=1;i<=q;i++){
    scanf("%lld%d",&t,&k);
    cout<<dp[find(t)][k]<<endl;
  }

}