Решение задачи Суммы с Меньшиков

Без пояснения   Просмотров: 198


Дано N целых чисел A1, A2, ..., AN. Требуется найти количество различных значений сумм вида k1A1 + k2A2 + ... + kNAN.

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
const int max_size = 50000 + 5;
int n;
vector<int> mas;
void input()
{
    cin>>n;
    mas.resize(n);
    for (int i=0;i<n;i++)
        scanf("%d", &mas[i]);
}
void solve()
{
    vector<int> met(max_size);
    met[0] = 1;
    int maxValue = 0;
    for (int j = 0; j<mas.size();j++)
    {
        int newMaxValue = maxValue;
        for (int i = maxValue;i>=0;i--)
        {
            if (met[i])
            {
                met[i + mas[j]] = 1;
                newMaxValue = max(i + mas[j], newMaxValue);
            }
        }
        maxValue = newMaxValue;
    }
 
    int difAmount = 0;
    for (int i=0;i<met.size();i++)
        if (met[i])
            difAmount++;
    cout<<difAmount;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться