【洛谷P1417】烹调方案贪心+背包dp

题目大意：一共有 n 件食材，每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t*bi的美味指数，用第i件食材做饭要花去ci的时间。众所周知，gw的厨艺不怎么样，所以他需要你设计烹调方案使得美味指数最大。

题解：这道题需要对背包问题有更加深入的理解。

可以发现，如果不进行排序操作的话，先选的物品会对后续选择的物品的价值产生影响，即：答案与选择的先后顺序有关。这与 0-1 背包问题不同，对于 0-1 背包问题来说，先选择的物品对后续物品答案的贡献没有影响，因此与选择的顺序无关。对于这种物品之间价值会相互影响的情况，首先考虑固定一个子集，对集合内的元素按某种顺序排序，扩展到整个集合来说，即：先进行排序，再进行 dp 即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn=55;

const int maxx=1e5+10;

int T,n;

LL dp[maxx];

struct node{int a,b,c;}t[maxn];

bool cmp(const node &x,const node &y){

	return (LL)x.c*y.b<(LL)x.b*y.c;

}

void read_and_parse(){

	scanf("%d%d",&T,&n);

	for(int i=1;i<=n;i++)scanf("%d",&t[i].a);

	for(int i=1;i<=n;i++)scanf("%d",&t[i].b);

	for(int i=1;i<=n;i++)scanf("%d",&t[i].c);

	sort(t+1,t+n+1,cmp);

}

void solve(){

	for(int i=1;i<=n;i++)

		for(int j=T;j>=t[i].c;j--)

			dp[j]=max(dp[j],dp[j-t[i].c]+t[i].a-(LL)t[i].b*j);

	LL ans=0;

	for(int i=0;i<=T;i++)ans=max(ans,dp[i]);

	printf("%lld\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【洛谷P1417】烹调方案贪心+背包dp

最新文章

热门文章

巴特西

【洛谷P1417】烹调方案 贪心+背包dp

最新文章

热门文章

【洛谷P1417】烹调方案贪心+背包dp