N3P3 - Hilera

#include <bits/stdc++.h>

using namespace std;

#define tripla vector <int>
///Sin ficha, ficha común, ficha especial
#define sin 0
#define com 1
#define esp 2

int hilera(vector <int> numeros, int k, vector <int> &fichas)
{
    int n = numeros.size();
    vector <vector <tripla> > DP(n+1, vector <tripla> (k+2, {0, 0, 0}));
    vector <vector <vector <tripla> > > A(n+1, vector <vector <tripla> > (k+2, vector <tripla> (3, {-1, -1, -1})));

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<=k; j++)
        {
            ///i numeros, j fichas especiales
            ///No puedo ir de común a común (1 -> 1)
            ///Los demás movimientos están permitidos

            ///Partiendo de "Sin ficha"
            if(DP[i][j][sin] > DP[i+1][j][sin])
            {
                DP[i+1][j][sin] = DP[i][j][sin];
                A[i+1][j][sin] = {i, j, sin};
            }
            if(DP[i][j][sin]+numeros[i] > DP[i+1][j][com])
            {
                DP[i+1][j][com] = DP[i][j][sin]+numeros[i];
                A[i+1][j][com] = {i, j, sin};
            }
            if(DP[i][j][sin]+numeros[i] > DP[i+1][j+1][esp])
            {
                DP[i+1][j+1][esp] = DP[i][j][sin]+numeros[i];
                A[i+1][j+1][esp] = {i, j, sin};
            }

            ///Partiendo de "Ficha comun"
            if(DP[i][j][com] > DP[i+1][j][sin])
            {
                DP[i+1][j][sin] = DP[i][j][com];
                A[i+1][j][sin] = {i, j, com};
            }
            if(DP[i][j][com]+numeros[i] > DP[i+1][j+1][esp])
            {
                DP[i+1][j+1][esp] = DP[i][j][com]+numeros[i];
                A[i+1][j+1][esp] = {i, j, com};
            }

            ///Partiendo de "Ficha especial"
            if(DP[i][j][esp] > DP[i+1][j][sin])
            {
                DP[i+1][j][sin] = DP[i][j][esp];
                A[i+1][j][sin] = {i, j, esp};
            }
            if(DP[i][j][esp]+numeros[i] > DP[i+1][j][com])
            {
                DP[i+1][j][com] = DP[i][j][esp]+numeros[i];
                A[i+1][j][com] = {i, j, esp};
            }
            if(DP[i][j][esp]+numeros[i] > DP[i+1][j+1][esp])
            {
                DP[i+1][j+1][esp] = DP[i][j][esp]+numeros[i];
                A[i+1][j+1][esp] = {i, j, esp};
            }
        }
    }

    int fil = 0, col = 0, tip = 0;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=k; j++)
            for(int c=0; c<3; c++)
                if(DP[i][j][c] > DP[fil][col][tip])
                    fil = i, col = j, tip = c;

    fichas = vector <int> (n, 0);
    int maxSuma = DP[fil][col][tip];

    while(fil != 0)
    {
        fichas[fil-1] = tip;
        tripla res = A[fil][col][tip];
        fil = res[0];
        col = res[1];
        tip = res[2];
    }

    return maxSuma;
}
/**
Casos sencillos
A) 6 0 20 10 10 20 10 20 (K = 0)
B) 9 3 10 20 10 10 20 10 10 20 10 (K = 3)
C) 6 3 20 10 10 20 10 20 (K = 3)
D) 5 0 20 10 10 30 15 (K = 0)
E) 5 0 20 10 10 20 15 (K = 0)
F) 7 0 3 2 2 3 2 2 3 (K = 0)
G) 5 0 20 10 10 30 15 (K = 0)
**/

/**
//Función main auxiliar para testear
int main()
{
    int n, k;
    cin >> n >> k;
    vector <int> numeros(n);
    for(int i=0; i<n; i++)
        cin >> numeros[i];
    vector <int> fichas;
    int res = hilera(numeros, k, fichas);
    cout << res << endl;
    for(auto i:fichas)
        cout << i << " ";
    cout << endl;
}
**/