Pagini recente » Cod sursa (job #1802949) | Cod sursa (job #1934030) | Cod sursa (job #1211037) | Cod sursa (job #2204044) | Cod sursa (job #4057)
Cod sursa(job #4057)
#include <iostream>
#define INF 0x3f3f //32639
#define val 0xff //255
using namespace std;
#define in "subsir2.in"
#define out "subsir2.out"
#define NMAX 5001
int a[NMAX], best[NMAX], tata[NMAX];
int n, minim, poz, sol;
char ok[NMAX];
void Read();
void Dinamic();
void Write();
void Rec( int );
FILE *fout = fopen( out, "w" );
int main()
{
Read();
Dinamic();
Write();
fclose( fout );
return 0;
}
void Read()
{
FILE *fin = fopen( in, "r" );
fscanf( fin, "%d", &n );
int i;
minim = INF;
for ( i = 0; i < n; ++i )
{
fscanf( fin, "%d", &a[i] );
if ( a[i] >= minim ) continue;
ok[i] = 1;
minim = a[i];
}
fclose( fin );
}
void Dinamic()
{
int i, j, min;
sol = INF;
for ( i = n - 1; i >= 0; --i )
{
best[i] = min = INF; tata[i] = -1;
for ( j = i + 1; j < n; ++j )
{
if ( a[j] < a[i] ) continue;
if ( a[j] < min && (best[i] > best[j] + 1 || (best[i] == best[j] + 1 && a[j] < a[tata[i]])))
{
best[i] = best[j] + 1;
tata[i] = j;
}
if ( a[j] < min )
min = a[j];
}
if ( best[i] == INF ) //daca nu am gasit nici o pozitia j corespunzatoare
{
best[i] = 1;
tata[i] = i;
}
if ( ok[i] && ( sol > best[i] || ( sol == best[i] && a[i] < a[poz] ) ) )
{
sol = best[i];
poz = i;
}
}
}
void Write()
{
fprintf( fout, "%d\n", sol );
Rec( poz );
}
void Rec( int i )
{
fprintf( fout, "%d ", i + 1 );
if ( i == tata[i] ) return;
Rec( tata[i] );
}