string lpsLexicographicallySmallest(const string& s){ int n = (int)s.size(); int st = 0, maxLen = 1;
auto better = [&](int candSt, int candLen) { if (candLen != maxLen) return candLen > maxLen; return s.substr(candSt, candLen) < s.substr(st, maxLen); };
auto expand = [&](int l, int r) { while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; } int candSt = l + 1; int candLen = r - l - 1; if (better(candSt, candLen)) { st = candSt; maxLen = candLen; } };
for (int i = 0; i < n; ++i) { expand(i, i); // 奇数长度 expand(i, i + 1); // 偶数长度 } return s.substr(st, maxLen); }
boolisPal(const string& s){ int l = 0, r = (int)s.size() - 1; while (l < r) { if (s[l++] != s[r--]) returnfalse; } returntrue; }
voidsolve(){ int n; cin >> n;
string str; str.push_back(n < 0 ? 'b' : 'a');
int cur = abs(n), base; while (cin >> base) { str.push_back(char('a' + cur % base)); cur /= base; }
有 N 个任务,需要把这些任务调度到服务器上运行。每个任务有 CPU 需求 c_i、内存需求 m_i、任务价值 v_i。服务器 CPU 规格为 C,内存规格为 M,一台服务器可以运行多个任务并获得它们的总价值,条件是这些任务的 CPU 需求之和不超过 C,且内存需求之和不超过 M。一个任务只能运行在一台服务器上。
我们想知道,当服务器数量为 1 到 N 的每一种情况,其运行任务的最大总价值是多少,以帮助决策需要购买多少台服务器。换句话说,对于 K=1,2,…,N,假设有 K 台服务器,分别输出可运行任务的最大总价值。
输入描述
第一行包含三个整数 N,C,M(1 ≤ N ≤ 15, 1 ≤ C,M ≤ 10^6),分别表示任务数量、服务器 CPU 规格、服务器内存规格。
接下来 N 行,每行包含三个整数 c_i,m_i,v_i(1 ≤ c_i,m_i,v_i ≤ 10^6),表示每个任务的 CPU 需求、内存需求和任务价值。
输出描述
输出 N 行,每行一个整数,第 i 行表示服务器数量 K=i 时可运行任务的最大总价值。
样例1
输入:
1 2 3 4
3 3 10 1 4 1 2 5 2 2 6 4
输出:
1 2 3
5 7 7
题意概述
个任务,每个任务有 。每台服务器有 CPU 上限 、内存上限 。对于 ,分别求有 台服务器时可获得的最大总价值。