Pagini recente » Cod sursa (job #638485) | Cod sursa (job #1600518) | Cod sursa (job #1034938) | Cod sursa (job #2902852) | Cod sursa (job #2398136)
#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;
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] >= 1)
see(poz[x]);
}
int main(){
int i, j;
f >> n;
if( n == 1){ g << 1 << "\n" << 1; return 0;}
for(i = 1; i <= n ; i++)
f >> v[i];
best[n] = 1;
poz[n] = -1;
int cmax = 0;
int pozmax = 0;
for(i = n-1; i >= 1 ; i--){
best[i] = 1;
poz[i] = -1;
for(j = i + 1 ; j <= n ; j++)
if(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";
}
if( 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;
}