排序

class Solution {
public:int minimumBoxes(vector<int> &apple, vector<int> &capacity) {int s = accumulate(apple.begin(), apple.end(), 0);sort(capacity.begin(), capacity.end(), greater<int>());int res = 0;for (int cur = 0, i = 0; i < capacity.size(); i++) {cur += capacity[i];res++;if (cur >= s)break;}return res;}
};

贪心：优先选幸福值较大的孩子，降序排序然后边遍历

class Solution {
public:long long maximumHappinessSum(vector<int> &happiness, int k) {long long res = 0;sort(happiness.begin(), happiness.end(), greater<int>());for (int i = 0; i < k; i++)res += max(0, happiness[i] - i);return res;}
};

哈希 + 二分：设 $cnt[s]$ 为 $arr$ 中包含子字符串 $s$ 的元素数，遍历 $arr$ 中的字符串 $s$ ，枚举其所有子字符串，并更新 $cnt$ ，遍历 $arr$ 中的字符串 $s$ ，二分搜素最短长度 $mid$ ，然后枚举 $s$ 长为 $mid$ 的子字符串，判断是否存在满足条件的子字符串

class Solution {
public:vector<string> shortestSubstrings(vector<string> &arr) {int mxn = 0;unordered_map<string, int> cnt;for (auto &s: arr) {mxn = max(mxn, (int) s.size());unordered_set<string> tmp;for (int i = 0; i < s.size(); i++) {//枚举s的子字符串string cur = "";for (int j = i; j < s.size(); j++) {//s[i,j]cur.push_back(s[j]);tmp.insert(cur);}}for (auto &subs: tmp)//更新cntcnt[subs]++;}vector<string> res;for (auto &s: arr) {int l = 1, r = s.size() + 1;string res_i;while (l < r) {//二分搜素满足条件的子字符串的最短长度int mid = (l + r) / 2;string cur_res;for (int i = 0; i + mid - 1 < s.size(); i++) {if (auto subs = s.substr(i, mid);cnt[subs] == 1) {if (cur_res.empty() || subs < cur_res)//满足条件且字典序最小cur_res = subs;}}if (!cur_res.empty()) {r = mid;res_i = cur_res;} elsel = mid + 1;}res.push_back(l != s.size() + 1 ? res_i : "");}return res;}
};

动态规划： 设 $p[i+1][j][tag]$ 表示在 $nums[0,i]$ 中选择 $j$ 个不相交的子数组的最大能量值（tag为 $0$ 表示选择的数中不包含 $nums[i]$ ，tag为 $1$ 表示选择的数中包含$nums[i]$）。

class Solution {
public:using ll = long long;ll inf = INT64_MIN;long long maximumStrength(vector<int> &nums, int k) {vector<ll> vx;for (int i = k, pos = 1; i >= 1; i--, pos ^= 1)vx.push_back(pos == 1 ? i : -1 * i);int n = nums.size();ll p[n + 1][k + 1][2];for (int i = 0; i <= n; i++)for (int j = 0; j <= k; j++)for (int t = 0; t < 2; t++)p[i][j][t] = inf;//初始化标志for (int i = 0; i <= n; i++)p[i][0][0] = p[i][0][1] = 0;//未选择的情况for (int i = 0; i < n; i++) {for (int j = 1; j <= min(i + 1, k); j++) {p[i + 1][j][1] = p[i][j - 1][1] + nums[i] * vx[j - 1];//nums[i] 为一个新选择的子数组的首元素if (p[i][j][1] != inf)p[i + 1][j][1] = max(p[i + 1][j][1], p[i][j][1] + nums[i] * vx[j - 1]);//nums[i]为上一个选择的子数组中的元素if (p[i][j - 1][0] != inf)p[i + 1][j][1] = max(p[i + 1][j][1], p[i][j - 1][0] + nums[i] * vx[j - 1]);//nums[i]为一个新选择的子数组的首元素p[i + 1][j][0] = max(p[i][j][0], p[i][j][1]);}}ll res = inf;for (int i = k - 1; i < n; i++)res = max({res, p[i + 1][k][0], p[i + 1][k][1]});return res;}
};