洛谷P1417 烹调方案

朴灿烈づ我的快乐病毒、 2022-05-27 06:23 124阅读 0赞

## 题目背景 ##

由于你的帮助，火星只遭受了最小的损失。但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改编

思路：dp，得先排序

参考：https://www.luogu.org/blog/kkksc03/solution-p1417\#

By tinylic

如果没有b\[i\]这个属性的话就是明显的01背包问题。

现在考虑相邻的两个物品x,y。假设现在已经耗费p的时间，那么分别列出先做x,y的代价：

a\[x\]-(p+c\[x\])\*b\[x\]+a\[y\]-(p+c\[x\]+c\[y\])\*b[y][]

a\[y\]-(p+c\[y\])\*b\[y\]+a\[x\]-(p+c\[y\]+c\[x\])\*b[x][]

对这两个式子化简，得到①＞②的条件是c\[x\]\*b\[y\]<c\[y\]\*b\[x\].

发现只要满足这个条件的物品对(x,y)，x在y前的代价永远更优。

因此可以根据这个条件进行排序，之后就是简单的01背包了。

写法一：一维dp

#include<iostream>
    #include<algorithm>
    #define Maxn 52
    using namespace std;
    typedef long long LL;
    int T;
    int n;
    
    struct node
    {
    	LL a, b, c;
    }dish[55];
    
    LL dp[100009];
    LL ans;
    
    int cmp(node x, node y)
    {
    	return x.c*y.b < x.b*y.c;
    }
    
    int main()
    {
    	//freopen("1.txt","r",stdin);
    	cin >> T >> n;
    
    	for (int i = 1; i <= n; i++)
    		cin >> dish[i].a;
    
    	for (int i = 1; i <= n; i++)
    		cin >> dish[i].b;
    
    	for (int i = 1; i <= n; i++)
    		cin >> dish[i].c;
    
    	sort(dish + 1, dish + 1 + n, cmp);
    
    	for (int i = 1; i <= n;i++)
    	for (int j = T; j >= dish[i].c; j--)
    	{
    		dp[j] = max(dp[j], dp[j - dish[i].c] + dish[i].a - j*dish[i].b);
    		ans = max(ans, dp[j]);
    	}
    
    	//for (int i = 1; i <= T; i++) ans = max(ans, dp[i]);
    	cout << ans;
    	return 0;
    }

写法二：二维dp

#include<iostream>
    #include<algorithm>
    #define Maxn 52
    using namespace std;
    typedef long long LL;
    int T;
    int n;
    
    struct node
    {
    	LL a, b, c;
    }dish[55];
    
    LL dp[Maxn][100009];
    LL ans;
    
    int cmp(node x, node y)
    {
    	return x.c*y.b < x.b*y.c;
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	cin >> T >> n;
    
    	for (int i = 1; i <= n; i++)
    		cin >> dish[i].a;
    
    	for (int i = 1; i <= n; i++)
    		cin >> dish[i].b;
    
    	for (int i = 1; i <= n; i++)
    		cin >> dish[i].c;
    
    	sort(dish + 1, dish + 1 + n, cmp);
    
    	for (int i = 1; i <= n; i++)
    	for (int j = 1; j<=T; j++)
    	{
    		dp[i][j] = dp[i - 1][j];
    		if (j>=dish[i].c)
    		dp[i][j] = max(dp[i][j], dp[i - 1][j - dish[i].c] + dish[i].a - j*dish[i].b);
    	}
    		
    	for (int i = 1; i <= T; i++) ans = max(ans, dp[n][i]);
    
    	cout << ans;
    
    	return 0;
    }

[y]: https://www.luogu.org/blog/kkksc03/%E2%91%A0
[x]: https://www.luogu.org/blog/kkksc03/%E2%91%A1