题目大意:给定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)

#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;
	}

	
	
	
	
	
}
最后修改日期:2020年5月31日