KCC3 :: Эдиториал, задача 3
Пингвины против полярников
Условия: http://esci.ru/kcc3/kcc3_t.php
Максимум найти просто: достаточно просуммировать min(R, N) самых многочисленных видов. Минимум несколько сложнее: для этого, используя ДП, найдем минимальную сумму численностей видов, которая ≥R. Это можно сделать, например, перебирая последний вид, и на каждом шаге добавляя к уже существующим суммам численность текущего (до 1003 итераций). Код достаточно прост.
Условия: http://esci.ru/kcc3/kcc3_t.php
Максимум найти просто: достаточно просуммировать min(R, N) самых многочисленных видов. Минимум несколько сложнее: для этого, используя ДП, найдем минимальную сумму численностей видов, которая ≥R. Это можно сделать, например, перебирая последний вид, и на каждом шаге добавляя к уже существующим суммам численность текущего (до 1003 итераций). Код достаточно прост.
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
int r, n;
cin >> r >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end(), greater<int>());
int ms = accumulate(a.begin(), a.end(), 0);
vector<int> dp(ms + 1, -1); dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= ms; ++j) {
if (dp[j] != -1 && dp[j] <= i) dp[j + a[i]] = i + 1;
}
}
int maxres = 0, minres = ms;
for (int j = r; j <= ms; ++j) {
if (dp[j] != -1) minres = j; break;
}
for (int i = 0, end = min(r, n); i < end; ++i) {
maxres += a[i];
}
cout << minres << " " << maxres << endl;
}
#include <vector>
#include <functional>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
int r, n;
cin >> r >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a.begin(), a.end(), greater<int>());
int ms = accumulate(a.begin(), a.end(), 0);
vector<int> dp(ms + 1, -1); dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= ms; ++j) {
if (dp[j] != -1 && dp[j] <= i) dp[j + a[i]] = i + 1;
}
}
int maxres = 0, minres = ms;
for (int j = r; j <= ms; ++j) {
if (dp[j] != -1) minres = j; break;
}
for (int i = 0, end = min(r, n); i < end; ++i) {
maxres += a[i];
}
cout << minres << " " << maxres << endl;
}
