P1417 烹调方案 题解
难度：⭐⭐⭐⭐
知识点：DP
题目链接
序言：
最近在练DP，刷到了这道题，众所周知，DP最重要的是有大佬给出能推出状态转移方程，这题就是这样的一题~
1.入手程序
一看：嗯~是一道明显的DP
再看：咦~好像不对劲，这是什么？
如果在t时刻完成第i样食材则得到ai-t*bi的美味指数
一想：啊~ 原来不是基本DP啊，看起来好难溜了溜了
再想：嘿~ 怎么能这样轻易放弃呢！
开始推状态转移方程！
2.编程思路
首先，这个题状态转移方程难推的地方在于，因为有b[i]的存在，一件食材先后制作获得的美味指数不同，那么~
sort大法好！
cmp怎么写呢？
慢慢推吧~
（强烈建议此时在看题解的你停下来推一下）
推完了么？
往下看吧????
关于每两个食材i和j，先做i和先做j的美味指数分别为：
1.a[i]-(t+c[i])*b[i]+a[j]-(t+c[i]+c[j])*b[j]
2.a[j]-(t+c[j])*b[j]+a[i]-(t+c[i]+c[j])*b[i]
如果1>2：
a[i]-t*b[i]-c[i]*b[i]+a[j]-t*b[j]-c[i]*b[j]-c[j]*b[j]>
a[j]-t*b[j]-c[j]*b[j]+a[i]-t*b[i]-c[i]*b[i]-c[j]*b[i]
↓
-t*b[i]-c[i]*b[i]-t*b[j]-c[i]*b[j]-c[j]*b[j]>
-t*b[j]-c[j]*b[j]-t*b[i]-c[i]*b[i]-c[j]*b[i]
↓
-c[i]*b[j]>-c[j]*b[i]
ok~
羌湖~ 起飞~
嗯嗯，还有一句话想说
十年OI一场空，不开long long见祖宗
3.AC代码
#include<bits/stdc++.h>
using namespace std;
struct Node
{
long long a,b,c;
}s[55];
long long t,n;
long long dp[100005];
long long ans;
bool cmp(Node x,Node y)
{
return -x.c*y.b>-y.c*x.b;//这短短的一行，我推了多久啊。。。
}
int main()
{
//读入
cin>>t>>n;
for(long long i=1;i<=n;i++)//其实这些地方可以不开long long
{
cin>>s[i].a;
}
for(long long i=1;i<=n;i++)
{
cin>>s[i].b;
}
for(long long i=1;i<=n;i++)
{
cin>>s[i].c;
}
//排序
sort(s+1,s+1+n,cmp);//sort大法好！
//01背包dp
for(long long i=1;i<=n;i++)
{
for(long long j=t;j>=s[i].c;j--)
{
dp[j]=max(dp[j],dp[j-s[i].c]+s[i].a-s[i].b*j);
ans=max(ans,dp[j]);
}
}
//输出
cout<<ans;
return 0;
}
