題目大意

一共有 $n$ 件食材，每件食材有三個屬性，$a_i$，$b_i$ 和 $c_i$，如果在 $t$ 時刻完成第 $i$ 樣食材則得到 $a_i?t\times b_i$ 的美味指數，用第 $i$ 件食材做飯要花去 $c_i$ 的時間。
需要設計烹調方案使得在$T$的時間內美味指數最大并輸出。

數據范圍及約定

• 對于 $40\%$ 的數據 $1\le n\le 10$；
• 對于 $100\%$ 的數據 $1\le n\le 50$。

所有數字均小于 $10^5$。

暴力想法

首先我們可以觀察到，若不考慮烹飪順序，或是已知順序的情況下，求解是很簡單的：只需要使用復雜度O(n^2)的01背包進行dp即可

（如果不知道01背包，強烈建議跳轉主頁學習）

注意到前40%數據的N很小，我們便可以直接暴力枚舉菜品的全排列，進行dp即可。

想明白后，我們稍加計算，就會發現：

超時辣！

時間復雜度$O(n^2{2}^n)$是過不了噠！（理論上超3e8次運算，數據很水就當我沒說）

正解

其實剛剛的想法已經比較接近正解了。我們來看看上面的做法能怎么優化。

對于后半部分，可以基本確定是沒有優化空間的——首先dp是必做，其次就算能將dp優化到$O(nlogn)$甚至$O(n)$，大數據依舊是過不了的。

于是我們考慮如何排列烹飪順序。

首先可以觀察到一個性質：如果交換相鄰兩個菜品的烹飪順序，對前后菜品產生的貢獻是沒有影響的，因為交換后此前烹飪的總時間不變！

也就是說，如果存在菜品A優于B（即先烹飪A價值更大）、B優于C，則一定有A優于C!

接下來我們開始推理每種菜品的應有順序。

假設有兩個相鄰的菜品序號為 $i,j$ ，之前所用的總時間為$T$

根據題意可得，若先烹飪$i$號菜品，得到的價值一共是：

$w_1=(a_i?b_i\times (T+c_i))+(a_j?b_j\times (T+c_i+c_j))$
$=a_i+a_j?T\times (b_i+b_j)?b_i\times c_i?b_j\times c_i?b_j\times c_j$

若先烹飪$j$號菜品，得到的價值一共是：

$w_2=(a_j?b_j\times (T+c_j))+(a_i?b_i\times (T+c_j+c_i))$
$=a_i+a_j?T\times (b_i+b_j)?b_i\times c_i?b_i\times c_j?b_j\times c_j$

顯然，若先烹飪$i$號更優，則有$w_1>w_2$

帶入并化簡兩邊，可以得到 $?b_j\times c_i>?b_i\times c_i$，

即：若$b_j\times c_i<b_i\times c_j$，則先烹飪$i$號菜品更優。

所以，我們可以先根據上述結論對數組排序，再做dp

時間復雜度$O(nT)$（畢竟$n$很小，排序時間可以不計）

AC代碼

#include<bits/stdc++.h>
using namespace std;
#define For(i, j, k) for(int i = j; i <= k; i++)
#define dFor(i, j, k)for(int i = j; i >= k; i--)
#define MaxN 55
#define int long longstruct Node{int a, b, c;bool operator<(const Node x) const{		//重載運算符，按之前的結論排序return c * x.b < b * x.c;}
}a[MaxN];
int T, n;
int f[MaxN][100005];signed main()
{cin >> T >> n;For(i, 1, n) cin >> a[i].a;For(i, 1, n) cin >> a[i].b;For(i, 1, n) cin >> a[i].c;sort(a+1, a+n+1);int ans = 0;For(i, 1, n){For(j, 1, T){				//01背包，雖然沒有降維優化awaf[i][j] = max(f[i][j], f[i-1][j]);if(j >= a[i].c){f[i][j] = max(f[i][j], f[i-1][j-a[i].c] + a[i].a-a[i].b*j);}ans = max(ans, f[i][j]);}}cout << ans << endl;return 0;
}

總結

思維難度相對較高，主要在于推理傳遞性和排序規則

類似的題目還有P1060國王游戲等，可以練習

最后，制作實在不易。如果你喜歡這篇文章，可以點個免費的關注和免費的贊

我們下期再見！