【题解】洛谷P1417烹调方案 01背包+贪心

题目链接

最初以为这就是一个01背包问题。设 $dp[i,j]$dp[i,j] 表示前 $i$i 项食材用时为 $j$j 时的最大美味指数。
$dp[i,j]=\max\limits_{c[i]\leq j\leq t}\{dp[i-1][j-c[i]]+a[i]-j\times b[i]\}$dp[i,j]=c[i]≤j≤tmax​{dp[i−1][j−c[i]]+a[i]−j×b[i]}
问题来了，这里物品的价值不是固定的，而是与选取的时间有关系。于是我们想到贪心的选择，利用邻项交换微扰法来证明贪心策略。
设连续选取的两个食材为 $x,y$x,y。
如果先选取 $x$x 更优，那么有：
$a[x]-j\times b[x]+a[y]-(j+c[x])\times b[y]>a[y]-j\times b[y]+a[x]-(j+c[y])\times b[x]$a[x]−j×b[x]+a[y]−(j+c[x])×b[y]>a[y]−j×b[y]+a[x]−(j+c[y])×b[x]
化简得到：
$c[x]\times b[y]&lt;c[y]\times b[x]$c[x]×b[y]<c[y]×b[x]
按照以上贪心策略排序后进行DP即可。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,t;
ll f[N],ans;
struct node{
	ll a,b,c;
	bool operator<(const node&rhs)const{
	return c*rhs.b<b*rhs.c;}
}p[N];
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&t,&n);
	for(int i=1;i<=n;i++)
	    scanf("%lld",&p[i].a);
	for(int i=1;i<=n;i++)
	    scanf("%lld",&p[i].b);
	for(int i=1;i<=n;i++)
	    scanf("%lld",&p[i].c);
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++)
	    for(ll j=t;j>=p[i].c;j--)
	        f[j]=max(f[j],f[j-p[i].c]+p[i].a-j*p[i].b);
	for(int j=0;j<=t;j++)
	    ans=max(ans,f[j]);
	printf("%lld\n",ans);
	return 0;
}

总结

本题和普通01背包区别在于物品的价值不是固定的，而是随选取时间改变而改变。此时通过贪心策略找到最优选取顺序再进行DP。