Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int main() {
- int L, n; // L - длина нити n - количество разных отрезков на которые мы можем делить
- cin >> L >> n;
- int dp[L + 1]; // Массив в котором храним ответ, сколько максимум цены можно набрать для веса dp[i]
- memset(dp, 0, sizeof dp); // пока не знаем ответ поэтому максимум можнем набрать 0
- int w[n], c[n]; // длина отрезка i и его цена
- // ввод
- for(int i = 0; i < n; i++) {
- cin >> w[i] >> c[i];
- }
- // рекурентное соотношение
- // для каждого веса i считаем сколько максимум цены можно набрать используя первые j предметов
- for(int i = 0; i <= L; i++) {
- // считаем для веса i
- for(int j = 0; j < n; j++) {
- //рассматриваем отрезок j
- // если его длина больше i, то мы не можем его взять, т.к он больше нашей текущей длины
- // если его длина больше i то или ответ остается текущим или мы смотрим сколько можно набрать цены если рассматривать отрезок длины i - w[j]
- if(w[j] <= i) dp[i] = max(dp[i], dp[i - w[j]] + c[j]);
- }
- }
- int ans = 0;
- // ищем ответ среди всех длин
- for(int i = 0; i <= L; i++) {
- ans = max(ans, dp[i]);
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement