Cod sursa(job #1325799)

Utilizator theprdvtheprdv theprdv Data 24 ianuarie 2015 13:01:19
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>

using namespace std;
fstream fout("subsir2.out", ios::out);

int v[5010], n, t[5010], p[5010], s[5010];
int maxx(int a, int b)
{
    if(a>b) return a;
    return b;
}
void ReadData()
{
    ifstream fin("subsir2.in");
    fin>>n;
    for (int i=1; i<=n; ++i)
        fin>>v[i];
    fin.close();
}
void first(int s){
    if(t[s]) first(t[s]);
        fout<<s<<" ";
}
int main()
{
    ReadData();
    for(int i=1; i<=n; i++)
        for(int j=i-1; j>=0; j--)
            if(v[i]>v[j] && (p[j]>p[i] || p[i]==0 || (s[j]+v[i]<s[i] && j!=0 && p[i]==p[j]))){
                s[i]=s[j]+v[i];
                t[i]=j;
                p[i]=p[j]+1;
            }

    int max=0, smin=s[1], poz;
    for(int i=1; i<=n; i++)
    if(s[i]<smin || p[i]>max){
        max=p[i]; smin=s[i]; poz=i;
    }
    fout<<max<<endl;
    first(poz);

    fout.close();
    return 0;
}