Рекуррентные соотношения и динамическое программирование

a[i] = max(a[i-2], a[i-3]) + candies[i]

#include <sstream>
bool jumps(size_t posv,vector<int> v,int *a,int posa,int sum,int&max,int&pmax)
{
    sum+=v[posv];
    if(posv>=v.size()-2)
    {
        if(sum>max)
        {
            pmax=posa;
            a[posa]=v[posv];
            max=sum;
            return true;
        }
        return false;
    }
    bool wasmax=false;
    for(int i=2; i<4; i++)
    if(posv+i<v.size())
        if(jumps(posv+i,v,a,posa+1,sum,max,pmax))
        {
            wasmax=true;
            a[posa]=v[posv];
        }
    return wasmax;
}
void main(int argc,char* argv[])
{
    ifstream fin("data.txt");
    string line;
    std::getline(fin, line);
    int n=atoi(line.c_str());
    for(int i=0; i<n; i++)
    {
        std::getline(fin, line);
        cout<<line<<endl;
        vector<int> v;
        istringstream ss(line);
        string sint;
        while(ss>>sint) v.push_back(atoi(sint.c_str()));
        int *a=new int[v.size()];
        int p,max=0;
        jumps(0,v,a,0,0,max,p);
        for(int i=0; i<=p; i++) cout<<a[i]<<" ";
        cout<<endl;
        delete[] a;
    }
    fin.close();
    system("pause");
}

///////////////////////////////////////////////////////////////////////////////
//1.
///////////////////////////////////////////////////////////////////////////////
//Формулировка задачи:
//Есть заяц, которому нужно пересечь реку, прыгая по островкам. На каждом
//островке находится определенное кол-во конфет, которые заяц собирает,
//попадая на него.
//Однако, заяц не может прыгнуть с островка i на островок i+1, заяц может
//прыгать через один остроков, т.е. c i на i+2 или через два островка, т.е.
//с i на i+3, как показано на рисунке ниже
//Рекуррентные соотношения и динамическое программирование
 
//Нужно найти максимальное количество конфет, которое может собрать заяц,
//перебираясь через реку. При этом свой путь, заяц должен заканчивать
//на n -ом или на n-1 -ом островке, где n - количество островков.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <map>
#include <utility>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector < int   >                           T_islet_values;
typedef T_islet_values::size_type                       T_islet_ind;
typedef int                                             T_jump_ind;
 
typedef std::pair   < T_jump_ind,       T_islet_ind >   T_jump_and_islet_indexes;
typedef std::map    < T_jump_and_islet_indexes, int >   T_res_of_jump_and_islet_indexes;
///////////////////////////////////////////////////////////////////////////////
T_islet_values    get_rand_islet_values( int    islets_total )
{
    const   int     BONBONS_PER_ISLET_MAX   {10};
    T_islet_values  res                     ( islets_total );
 
    std::generate
        (
            res.begin   (),
            res.end     (),
 
            [=]
            {
                return  rand()  %   BONBONS_PER_ISLET_MAX   +   1;
            }
        );
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
void    print_islet_values( T_islet_values  const   &   islet_values )
{
    std::copy
        (
            islet_values.begin              (),
            islet_values.end                (),
            std::ostream_iterator< int >    ( std::cout, " " )
        );
 
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_jump
    (
        T_jump_ind                                      jump_ind,
        T_islet_ind                                     islet_ind_prev,
        int                                             res_prev,
 
        T_islet_values                      const   &   islet_values,
        T_res_of_jump_and_islet_indexes             &   res_of_jump_and_islet_indexes,
        int                                         &   res
    )
{
    const   int     JUMP_DELTA_MIN  {2};
    const   int     JUMP_DELTA_MAX  {3};
    bool            bool_res        {};
 
    for( int  delta = JUMP_DELTA_MIN; delta <= JUMP_DELTA_MAX; ++delta )
    {
        auto        islet_ind   =   islet_ind_prev  +   delta;
 
        if  (
                islet_ind   >=  islet_values.size()
            )
        {
            break;
        }
 
        bool_res                =   true;
 
        auto        new_res     =       res_prev
                                    +   islet_values[ islet_ind ];
 
        auto    &   res_ref     =   res_of_jump_and_islet_indexes
                                        [
                                            std::make_pair
                                                (
                                                    jump_ind,
                                                    islet_ind
                                                )
                                        ];
 
        if  (
                    new_res
                >   res_ref
            )
        {
            res_ref     =   new_res;
        }
    }//for
 
    if  (
                !bool_res
            &&  res_prev    >   res
        )
    {
        res     =   res_prev;
    }
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     collected_bonbons_max( T_islet_values  const   &   islet_values )
{
    int                                 res{};
    T_res_of_jump_and_islet_indexes     res_of_jump_and_islet_indexes;
    T_jump_ind                          jump_ind_start      {};
    T_islet_ind                         islet_ind_start     {};
 
    res_of_jump_and_islet_indexes
        [
            std::make_pair
                (
                    jump_ind_start++,
                    islet_ind_start
                )
        ]
        =   islet_values[ islet_ind_start ];
 
 
    for ( T_jump_ind  j{ jump_ind_start };; ++j )
    {
        bool    were_jumping{};
 
        for (
                auto
                it  =   res_of_jump_and_islet_indexes.rbegin    ();
                it  !=  res_of_jump_and_islet_indexes.rend      ();
                ++it
            )
        {
            if  (
                    it->first.first     !=  j - 1
                )
            {
                break;
            }
 
            if  (
                    successfully_jump
                        (
                            j,
                            it->first.second,
                            it->second,
 
                            islet_values,
                            res_of_jump_and_islet_indexes,
                            res
                        )
                )
            {
                were_jumping    =   true;
            }
        }//for
 
        if( !were_jumping )
        {
            break;
        }
    }//for
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        int     islets_total{};
 
        do
        {
            std::cout   <<  "islets total (>0): ";
            std::cin    >>  islets_total;
        }
        while( islets_total     <=  0 );
 
        T_islet_values    islet_values  =   get_rand_islet_values( islets_total );
        print_islet_values( islet_values );
 
        std::cout   <<  "-> "
                    <<  collected_bonbons_max( islet_values )
                    <<  std::endl
                    <<  std::endl;
    }//for
}

 std::map<std::pair<int, size_t>, int>

///////////////////////////////////////////////////////////////////////////////
//2.
///////////////////////////////////////////////////////////////////////////////
//Формулировка задачи:
//Есть заяц, которому нужно пересечь реку, прыгая по островкам. На каждом
//островке находится определенное кол-во конфет, которые заяц собирает,
//попадая на него.
//Однако, заяц не может прыгнуть с островка i на островок i+1, заяц может
//прыгать через один остроков, т.е. c i на i+2 или через два островка, т.е.
//с i на i+3, как показано на рисунке ниже
//Рекуррентные соотношения и динамическое программирование
 
//Нужно найти максимальное количество конфет, которое может собрать заяц,
//перебираясь через реку. При этом свой путь, заяц должен заканчивать
//на n -ом или на n-1 -ом островке, где n - количество островков.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <map>
#include <utility>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector < int   >                           T_islet_values;
typedef T_islet_values::size_type                       T_islet_ind;
typedef int                                             T_jump_ind;
 
typedef std::pair   < T_jump_ind,       T_islet_ind >   T_jump_and_islet_indexes;
typedef std::map    < T_jump_and_islet_indexes, int >   T_res_of_jump_and_islet_indexes;
///////////////////////////////////////////////////////////////////////////////
T_islet_values    get_rand_islet_values( int    islets_total )
{
    const   int     BONBONS_PER_ISLET_MAX   {10};
    T_islet_values  res                     ( islets_total );
 
    std::generate
        (
            res.begin   (),
            res.end     (),
 
            [=]
            {
                return  rand()  %   BONBONS_PER_ISLET_MAX   +   1;
            }
        );
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
void    print_islet_values( T_islet_values  const   &   islet_values )
{
    std::copy
        (
            islet_values.begin              (),
            islet_values.end                (),
            std::ostream_iterator< int >    ( std::cout, " " )
        );
 
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_jump
    (
        T_jump_ind                                      jump_ind,
        T_islet_ind                                     islet_ind_prev,
        int                                             res_prev,
 
        T_islet_values                      const   &   islet_values,
        T_res_of_jump_and_islet_indexes             &   res_of_jump_and_islet_indexes
    )
{
    const   int     JUMP_DELTA_MIN  {2};
    const   int     JUMP_DELTA_MAX  {3};
    bool            bool_res        {};
 
    for( int  delta = JUMP_DELTA_MIN; delta <= JUMP_DELTA_MAX; ++delta )
    {
        auto        islet_ind   =   islet_ind_prev  +   delta;
 
        if  (
                islet_ind   >=  islet_values.size()
            )
        {
            break;
        }
 
        bool_res                =   true;
 
        auto        new_res     =       res_prev
                                    +   islet_values[ islet_ind ];
 
        auto    &   res_ref     =   res_of_jump_and_islet_indexes
                                        [
                                            std::make_pair
                                                (
                                                    jump_ind,
                                                    islet_ind
                                                )
                                        ];
 
        if  (
                    new_res
                >   res_ref
            )
        {
            res_ref     =   new_res;
        }
    }//for
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     collected_bonbons_max( T_islet_values  const   &   islet_values )
{
    int                                 res{};
    T_res_of_jump_and_islet_indexes     res_of_jump_and_islet_indexes;
    T_jump_ind                          jump_ind_start      {};
    T_islet_ind                         islet_ind_start     {};
 
    res_of_jump_and_islet_indexes
        [
            std::make_pair
                (
                    jump_ind_start,
                    islet_ind_start
                )
        ]
        =   islet_values[ islet_ind_start ];
 
    ++jump_ind_start;
 
    for ( T_jump_ind  j{ jump_ind_start };; ++j )
    {
        bool    were_jumping{};
 
        for (
                auto
                it  =   res_of_jump_and_islet_indexes.lower_bound
                            (
                                std::make_pair( j - 1, 0 )
                            );
 
                it  !=  res_of_jump_and_islet_indexes.end();
                ++it
            )
 
        {
            if  (
                    successfully_jump
                        (
                            j,
                            it->first.second,
                            it->second,
 
                            islet_values,
                            res_of_jump_and_islet_indexes
                        )
                )
            {
                were_jumping    =   true;
            }
            else if( it->second     >   res )
            {
                res     =   it->second;
            }
        }//for
 
        if( !were_jumping )
        {
            break;
        }
    }//for
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
            int     islets_total{};
 
        do
        {
            std::cout   <<  "islets total (>0): ";
            std::cin    >>  islets_total;
        }
        while( islets_total     <=  0 );
 
        T_islet_values    islet_values  =   get_rand_islet_values( islets_total );
        print_islet_values( islet_values );
 
        std::cout   <<  "-> "
                    <<  collected_bonbons_max( islet_values )
                    <<  std::endl
                    <<  std::endl;
    }//for
}

int     collected_bonbons_max( T_islet_values  const   &   islet_values )
{
    int                                 res{};
    int                                 j{1};
    T_res_of_jump_and_islet_indexes     res_of_jump_and_islet_indexes;
    T_jump_ind                          jump_ind_start      {};
    T_islet_ind                         islet_ind_start     {};
 
    res_of_jump_and_islet_indexes
        [
            std::make_pair
                (
                    jump_ind_start,
                    islet_ind_start
                )
        ]
        =   islet_values[ islet_ind_start ];
        
    for (
            auto
            it  =   res_of_jump_and_islet_indexes.lower_bound
                        (
                            std::make_pair( j - 1, 0 )
                        );
 
            it  !=  res_of_jump_and_islet_indexes.end();
            ++it
        )
 
    {
        if  (
                !successfully_jump
                    (
                        j,
                        it->first.second,
                        it->second,
 
                        islet_values,
                        res_of_jump_and_islet_indexes
                    )
                && it->second     >   res
            )
        {
            res     =   it->second;
        }
    }//for
 
    return  res;
}

///////////////////////////////////////////////////////////////////////////////
//4.
///////////////////////////////////////////////////////////////////////////////
//Формулировка задачи:
//Есть заяц, которому нужно пересечь реку, прыгая по островкам. На каждом
//островке находится определенное кол-во конфет, которые заяц собирает,
//попадая на него.
//Однако, заяц не может прыгнуть с островка i на островок i+1, заяц может
//прыгать через один остроков, т.е. c i на i+2 или через два островка, т.е.
//с i на i+3, как показано на рисунке ниже
//Рекуррентные соотношения и динамическое программирование
 
//Нужно найти максимальное количество конфет, которое может собрать заяц,
//перебираясь через реку. При этом свой путь, заяц должен заканчивать
//на n -ом или на n-1 -ом островке, где n - количество островков.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <map>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int   >                   T_islet_values;
typedef T_islet_values::size_type                   T_islet_ind;
typedef std::map        < T_islet_ind,  int     >   T_res_of_islet_ind;
///////////////////////////////////////////////////////////////////////////////
T_islet_values    get_rand_islet_values( int    islets_total )
{
    const   int     BONBONS_PER_ISLET_MAX   {10};
    T_islet_values  res                     ( islets_total );
 
    std::generate
        (
            res.begin   (),
            res.end     (),
 
            [=]
            {
                return  rand()  %   BONBONS_PER_ISLET_MAX   +   1;
            }
        );
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
void    print_islet_values( T_islet_values  const   &   islet_values )
{
    std::copy
        (
            islet_values.begin              (),
            islet_values.end                (),
            std::ostream_iterator< int >    ( std::cout, " " )
        );
 
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_jump
    (
        T_islet_ind                     islet_ind_prev,
        int                             res_prev,
 
        T_islet_values      const   &   islet_values,
        T_res_of_islet_ind          &   res_of_islet_ind
    )
{
    static  const   int     JUMP_DELTA_MIN  {2};
    static  const   int     JUMP_DELTA_MAX  {3};
    bool                    bool_res        {};
 
    for( int  delta = JUMP_DELTA_MIN; delta <= JUMP_DELTA_MAX; ++delta )
    {
        auto    islet_ind   =   islet_ind_prev  +   delta;
 
        if  (
                islet_ind   >=  islet_values.size()
            )
        {
            break;
        }
 
        bool_res                =   true;
 
        auto        new_res     =       res_prev
                                    +   islet_values[ islet_ind ];
 
        auto    &   res_ref     =   res_of_islet_ind[ islet_ind ];
 
        if  (
                    new_res
                >   res_ref
            )
        {
            res_ref     =   new_res;
        }
    }//for
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     collected_bonbons_max( T_islet_values  const   &   islet_values )
{
    int                 res{};
    T_res_of_islet_ind  res_of_islet_ind;
 
    res_of_islet_ind[0]     =   islet_values[0];
 
    for( auto   const   &   islet_ind_and_res   :   res_of_islet_ind )
    {
        auto    res_cur     =   islet_ind_and_res.second;
 
        if  (
                    !successfully_jump
                        (
                            islet_ind_and_res.first,
                            res_cur,
 
                            islet_values,
                            res_of_islet_ind
                        )
 
                &&      res_cur
                    >   res
            )
        {
            res     =   res_cur;
        }
    }//for
 
    return  res;
}///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
            int     islets_total{};
 
        do
        {
            std::cout   <<  "islets total (>0): ";
            std::cin    >>  islets_total;
        }
        while( islets_total     <=  0 );
 
        T_islet_values    islet_values  =   get_rand_islet_values( islets_total );
        print_islet_values( islet_values );
 
        std::cout   <<  "-> "
                    <<  collected_bonbons_max( islet_values )
                    <<  std::endl
                    <<  std::endl;
    }//for
}

return candies[candies.size()-1];

return candies[candies.size()-1];

return candies[candies.size()-1] > candies[candies.size()-2] ? candies[candies.size()-1] : candies[candies.size()-2];