題目背景

由于你的幫助，火星只遭受了最小的損失。但gw懶得重建家園了，就造了一艘飛船飛向遙遠的earth星。不過飛船飛到一半，gw發現了一個很嚴重的問題：肚子餓了~

gw還是會做飯的，于是拿出了儲藏的食物準備填飽肚子。gw希望能在T時間內做出最美味的食物，但是這些食物美味程度的計算方式比較奇葩，于是絕望的gw只好求助于你了。

題目描述

一共有n件食材，每件食材有三個屬性，ai，bi和ci，如果在t時刻完成第i樣食材則得到ai-t*bi的美味指數，用第i件食材做飯要花去ci的時間。

眾所周知，gw的廚藝不怎么樣，所以他需要你設計烹調方案使得美味指數最大

輸入輸出格式

輸入格式：
第一行是兩個正整數T和n，表示到達地球所需時間和食材個數。

下面一行n個整數，ai

下面一行n個整數，bi

下面一行n個整數，ci

輸出格式：
輸出最大美味指數

輸入輸出樣例

輸入樣例#1： 復制
74 1
502
2
47
輸出樣例#1： 復制
408
說明

【數據范圍】

對于40%的數據1<=n<=10

對于100%的數據1<=n<=50

所有數字均小于100,000

【題目來源】

tinylic改編

思路：如果沒有bi的話顯然是直接01背包，但有了bi的話就要考慮所選物品的先后順序，那么可以將物品進行優先度排序，現在假設前面已經用了時間t要比較先選x物體好還是y好
若先選x美味指數為： ai[x]-(t+ci[x])*bi[x]+ai[y]-(t+ci[x]+ci[y])*bi[y] —-①
若先選y美味指數為： ai[y]-(t+ci[y])*bi[y]+ai[x]-(t+ci[y]+ci[x])*bi[x] —-②
化簡①>②可以得到 ci[x]*bi[y] < bi[x]*ci[y]
有了這個式子后將原物體排序后用01背包求解即可

code:

#include<cstdio> #include<algorithm> #define ll long long using namespace std;int n,t; int dp[100005],ai[55],bi[55],ci[55]; ll maxn; struct ssc{int a,b,c; }sc[55];ll max(ll x,ll y){return x>y?x:y; }bool cmp(ssc x,ssc y){return y.b*x.c<x.b*y.c; }int main(){scanf("%lld %d",&t,&n);for(int i=1;i<=n;i++) scanf("%d",&sc[i].a);for(int i=1;i<=n;i++) scanf("%d",&sc[i].b);for(int i=1;i<=n;i++) scanf("%d",&sc[i].c);sort(sc+1,sc+1+n,cmp);for(int k=1;k<=n;k++) for(ll j=t;j;j--)if(j>=sc[k].c)dp[j]=max(dp[j],dp[j-sc[k].c]+sc[k].a-j*sc[k].b);for(ll i=1;i<=t;i++) maxn=max(dp[i],maxn);printf("%lld",maxn);return 0; }

轉載于:https://www.cnblogs.com/Menteur-Hxy/p/9248025.html

總結

以上是生活随笔為你收集整理的洛谷 P1417 烹调方案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。