题目：https://www.luogu.org/problemnew/show/P1417
题意：
一道菜有$a,b,c$三个值。烧一道菜的时间是$c$。得到的价值是，$a-t*b$其中$t$是菜完成的时间。
问用总时间t可以烧多少菜使得总价值最大。
思路：
很容易可以想到背包，一道菜做或是不做。
即$dp[t][i] = max(dp[t][i-1], dp[t-c_i][i-1]+a_i-t*b_i)$
但是由于$t$会影响到菜的价值，也就是说菜的顺序也是有影响的。所以并不是简单的背包。
考虑两道菜$x,y$，分别考虑先做$x$和先做$y$的情况，所得到的价值分别是：
$a_x-t*b_x+a_y-(t+c_x)*b_y$和$a_y-t*b_y+a_x-(t+c_y)*b_x$，可以发现这里可以贪心。
也就是如果$c_x*b_y > c_y*b_x$那么x在前可以得到更大的价值。按着个排个序再进行背包。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<map> 4 #include<set> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<stack> 10 #include<queue> 11 #include<iostream> 12 13 #define inf 0x7fffffff 14 using namespace std; 15 typedef long long LL; 16 typedef pair<string, string> pr; 17 18 int n, t; 19 const int maxn = 55; 20 const int maxt = 100005; 21 struct node{ 22 LL a, b, c; 23 }food[maxn]; 24 LL dp[maxt][maxn]; 25 26 bool cmp(node a, node b) 27 { 28 return a.c * b.b < b.c * a.b; 29 } 30 31 int main() 32 { 33 scanf("%d%d", &t, &n); 34 for(int i = 1; i <= n; i++){ 35 scanf("%lld", &food[i].a); 36 } 37 for(int i = 1; i <= n; i++){ 38 scanf("%lld", &food[i].b); 39 } 40 for(int i = 1; i <= n; i++){ 41 scanf("%lld", &food[i].c); 42 } 43 sort(food + 1, food + 1 + n, cmp); 44 45 for(int i = 1; i <= n; i++){ 46 for(int j = t; j >= 0; j--){ 47 if(j >= food[i].c)dp[j][i] = max(dp[j][i - 1], dp[j - food[i].c][i - 1] + food[i].a - (j) * food[i].b); 48 else dp[j][i] = dp[j][i - 1]; 49 } 50 } 51 LL ans = 0; 52 for(int j = 0; j <= t; j++){ 53 ans = max(ans, dp[j][n]); 54 } 55 printf("%lld\n", ans); 56 57 return 0; 58 }
原文：https://www.cnblogs.com/wyboooo/p/10839237.html