Pagini recente » Cod sursa (job #1710793) | Cod sursa (job #489595) | Cod sursa (job #624165) | Cod sursa (job #2372609) | Cod sursa (job #2418162)
#include <fstream>
using namespace std;
ifstream cin ("subsir2.in");
ofstream cout ("subsir2.out");
int n;
int v[5005], dp[5005];
int main() {
cin >> n;
for(int i = 1; i <= n; i++)
cin >> v[i], dp[i] = 5001;
dp[n] = 1;
for(int i = n - 1; i >= 1; i--) {
int mn = 1000000;
for(int j = i + 1; j <= n; j++) {
if(v[i] <= v[j] && v[j] < mn) {
mn = v[j];
dp[i] = min(dp[i], dp[j] + 1);
}
}
if(dp[i] == 5001)
dp[i] = 1;
}
int mn2 = 1000000, sol = 5000;
for(int i = 1; i <= n; i++) {
if(v[i] < mn2) {
mn2 = v[i];
sol = min(sol, dp[i]);
}
}
cout << sol << "\n";
int poz = 0, lst = -1000000;
while(sol) {
int val1 = 1000000, val2 = 1000000;
for(int i = poz + 1; i <= n; i++) {
if(dp[i] == sol && lst <= v[i] && v[i] < val1) {
val1 = val2 = v[i];
poz = i;
} else if(lst <= v[i] && v[i] < val1)
val1 = v[i];
}
cout << poz << " ";
lst = v[poz];
sol--;
}
return 0;
}