Pagini recente » Cod sursa (job #2447329) | Cod sursa (job #602213) | Cod sursa (job #192155) | Cod sursa (job #270534) | Cod sursa (job #2398169)
#include <fstream>
using namespace std;
ifstream f ("subsir2.in");
ofstream g ("subsir2.out");
int n, v[5005];
int best[5005], poz[5005], l[5005], pos, nr;
bool ok[5005];
const int inf = (1 << 30);
int minim;
int gasit ( int i, int j ){
int li = i;
if(j == i + 1) return 0;
for(i = li + 1; i < j; i++)
if(v[li] <= v[i] && v[i] <= v[j])
return 1;
return 0;
}
void see ( int x ){
g << x << " ";
if(poz[x] != x)
see (poz[x]);
}
int main(){
int i, j;
f >> n;
//if( n == 1){ g << 1 << "\n" << 1; return 0;}
minim = inf;
for(i = 1; i <= n ; i++){
f >> v[i];
if(v[i] < minim){
minim = v[i];
ok[i] = 1;
}
}
//best[n] = 1;
// poz[n] = -1;
int cmax = inf;
int pozmax = 0;
for(i = n; i >= 1 ; i--){
best[i] = inf;
minim = inf;
poz[i] = -1;
for(j = i + 1 ; j <= n ; j++){
if(v[j] < v[i]) continue;
if(minim > v[j] && (/*v[j] >= v[i] &&*/ (best[j] + 1 < best[i] || (best[i] == best[j] + 1 && v[j] < v[poz[i]]) ) /*&& !gasit(i,j)*/ )){
best[i] = best[j] + 1;
poz[i] = j; //g << j << " " << i << " " << gasit(i,j)<<"\n";
}
minim = min( minim, v[j] );
}
if( best[i] == inf){
best[i] = 1;
poz[i] = i;
}
if(ok[i] && ( best[i] < cmax || (best[i] == cmax && v[i] < v[pozmax]) )){
cmax = best[i];
pozmax = i;
}
}
g << cmax << "\n";
see(pozmax);
// g << pozmax << "\n";
//for(i = 1 ; i <= n; i++ )
// g << best[i] << " "; g << "\n";*/
//for(i = 1 ; i <= n; i++ )
// g << poz[i] << " ";
return 0;
}