Mai intai trebuie sa te autentifici.
Cod sursa(job #1489232)
Utilizator | Data | 20 septembrie 2015 19:58:13 | |
---|---|---|---|
Problema | Subsir 2 | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.64 kb |
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
#define inf 5050
using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int N;
int v[5010],best[5010],urm[5010];
// v=vectorul initial
// best[i]=lungimea subsirului maximal de lungime minima ( pe [i,N] ) care se termina la stanga in i
// urm[i]=pozitia elementului urmator lui i in subsirul in care se afla i
int main()
{
f>>N;
FOR (i,1,N) {
f>>v[i];
}
best[N]=1;
urm[N]=inf;
ROF (i,N-1,1) {
best[i]=inf;
urm[i]=inf;
int min1=inf;
FOR (j,i+1,N) {
if (v[i]<=v[j] && v[j]<min1) {
min1=v[j];
if (best[i]>=best[j]) {
best[i]=best[j];
urm[i]=j;
}
}
}
if (best[i]==inf) {
best[i]=1;
}
else {
++best[i];
}
}
int j=1,st=1;
int rez=best[1];
FOR (i,2,N) { // se cauta cel mai scurt subsir maximal care incepe de pe un element cat mai mic
if (v[j]>v[i]) {
j=i;
if (best[j]<=rez) {
rez=best[j];
st=i;
}
}
}
g<<rez<<'\n';
while (st!=inf) {
g<<st<<' ';
st=urm[st];
}
f.close();g.close();
return 0;
}