Pagini recente » Cod sursa (job #2494518) | Cod sursa (job #222257) | Cod sursa (job #353072) | Cod sursa (job #635718) | Cod sursa (job #1525068)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
const int inf = 0x3f3f3f3f;
const int maxn = 5005;
int dp[maxn];
int a[maxn];
int dad[maxn];
int main()
{
int n;
in >> n;
for(int i = 1; i <= n; i++)
in >> a[i];
/// dp[i] = cel mai mic subsirul crescator maximal care incepe
/// pe pozitia i
/// a[i] < a[k] < a[j]
/// dad[i] = din cine am venit
a[0] = -inf;
for(int i = n; i >= 1; i--)
{
dp[i] = inf;
int mn = inf;
dad[i] = 0;
for(int j = i + 1; j <= n ; j ++)
{
if(a[i] > a[j])
continue;
if(mn > a[j]) {
if(dp[i] > dp[j] + 1 || (dp[i] == dp[j] + 1 && a[ dad[i] ] > a[j])) {
dad[i] = j;
dp[i] = dp[j] + 1;
}
}
mn = min(mn, a[j]);
}
if(dp[i] == inf)
dp[i] = 1;
}
/*** min(dp[j]) |
nu exista un k***
astfel incat
aa[j] - false*/
//for(int i = 1 ; i <= n ; ++ i)
// cout << dp[i] << ' ';
int minim = inf;
int mindp = inf;
int st = 0;
//cout << '\n';
for(int i = 1 ; i <= n ; ++ i) {
if(a[i] < minim) {
if(mindp > dp[i] || (mindp == dp[i] && a[st] > a[i])) {
mindp = dp[i];
st = i;
}
}
minim = min(minim, a[i]);
}
out << mindp << '\n';
out << st << ' ';
while(dad[st]) {
out << dad[st] << ' ';
st = dad[st];
}
return 0;
}