Pagini recente » Cod sursa (job #170691) | Cod sursa (job #1679176) | Cod sursa (job #752002) | Cod sursa (job #1146552) | Cod sursa (job #2214893)
#include <fstream>
using namespace std;
ifstream fin ("subsir2.in");
ofstream fout ("subsir2.out");
const int Dim = 5001;
int D[Dim], T[Dim],n,A[Dim],Used[Dim];
void Dynamic();
void Afis(int poz);
int main() {
fin >> n;
for ( int i = 1; i <= n; ++i)
fin >> A[i];
Dynamic();
int mi = 0x3f3f3f3f,poz;
for ( int i = 1; i <= n; ++i)
if ( mi > D[i] and !Used[i] ) {
mi = D[i];
poz = i;
}
fout << mi << "\n";
Afis(poz);
}
void Afis(int poz) {
fout << poz << " " ;
if ( T[poz] == 0) return;
Afis(T[poz]);
}
void Dynamic() {
for ( int i = n; i >= 1; --i) {
D[i] = 0x3f3f3f3f;
int mi = 0x3f3f3f3f, miA = 0x3f3f3f3f,poz;
for ( int j = i + 1; j <= n; ++j) {
if ( A[j] >= A[i] and A[j] < mi and D[j] < miA) {
miA = D[j];
Used[j] = 1;
poz = j;
}
else
if ( A[j] >= A[i] and A[j] < mi and D[j] == miA and A[poz] > A[j] )
poz = j,Used[j] = 1;
if ( A[j] >= A[i] and mi > A[j] )
mi = A[j];
}
D[i] = miA + 1;
T[i] = poz;
if ( miA == 0x3f3f3f3f )
D[i] = 1, T[i] = 0;
}
}