Pagini recente » drumarb2 | Cod sursa (job #47179) | Cod sursa (job #3005182) | Cod sursa (job #3227233) | Cod sursa (job #1399812)
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
const int INF = 0x3f3f3f3f;
int N;
int pos, sol;
int V[5005], dp[5005], TT[5005];
bool inSubsir[5005];
void solve()
{
int minim;
for (int i = N; i >= 1; --i)
{
dp[i] = INF;
minim = INF;
for (int j = i + 1; j <= N; ++j)
{
if (V[j] >= V[i])
inSubsir[j] = true;
if (V[j] >= V[i] && V[j] < minim)
{
minim = V[j];
if (dp[j] + 1 <= dp[i])
{
if (dp[j] + 1 < dp[i])
TT[i] = j;
else if (dp[j] + 1 == dp[i])
{
if (V[j] < V[TT[i]])
TT[i] = j;
}
dp[i] = dp[j] + 1;
}
}
}
if (dp[i] == INF)
{
dp[i] = 1;
TT[i] = N + 1;
}
}
sol = INF;
for (int i = 1; i <= N; ++i)
if (!inSubsir[i])
{
if (dp[i] <= sol)
{
if (dp[i] < sol)
pos = i;
else if (dp[i] == sol)
{
if (V[i] < V[pos])
pos = i;
}
sol = dp[i];
}
}
}
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> V[i];
solve();
fout << sol << '\n';
while (pos <= N)
{
fout << pos << ' ';
pos = TT[pos];
}
fout << '\n';
fin.close();
fout.close();
return 0;
}