Cod sursa(job #2143474)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 26 februarie 2018 00:12:28
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <fstream>
#define dimm 1005

std::ifstream f("sclm.in");
std::ofstream g("sclm.out");

int N, v[dimm];
int prec[dimm], dyn[dimm];

void citire() {
    f >> N;
    for (int i=0; i<N; i++)
        f >> v[i+1];
}
void rezolvare() {
    for (int i=N, j, vmax; i>0; i--) {
        vmax = 0; dyn[i] = 1;
        for (j=i+1; j<=N; j++)
            if(v[j]>v[i] && dyn[j] > vmax) {
                prec[i] = j;
                dyn[i] = dyn[j]+1;
                vmax = dyn[j];
            }
    } int vmax = 0, p;
    for (int i=1; i<=N; i++) {
        if(vmax < dyn[i]) {
            vmax = dyn[i];
            p = i;
        }
    } g << vmax << '\n';
    while(prec[p]) {
        g << p << ' ';
        p = prec[p];
    } g << p;
}

int main()
{
    citire();
    rezolvare();

    return 0;
}