Я практиковал DP в качестве повышения квалификации, так как это моя самая слабая техника в конкурентном программировании, и я наткнулся на проблему горного хребта на cses.fi. Он предоставил тестовый пример прост, и я мог бы выяснить, почему выходное значение было 5. Я посмотрел на другие тестовые случаи, когда отправил свой ответ, и некоторые из них были совершенно неверными. Моя методология, казалось, была правильной (хотя и медленнее, чем требуется), но это просто полностью озадачивает, как я предназначен для решения этой проблемы, когда тестовые случаи не имеют смысла при ручном обзоре. Поскольку 431 человек (на момент написания письма), которые решили эту проблему, я хотел бы некоторую помощь от одного из них (или кого -то способного) в объяснении точных условий проблемы и метода, используемого для решения, поскольку я застрял на ней, чтобы быть честным. /> и решение, которое я использовал: < /p>
#include
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector a(n);
for(int i = 0; i < n; i++) {
cin >> a;
}
vector dp;
int grt, maxSize = 0;
for(int i = 0; i < n; i++) {
if(dp.size() == 0) {
dp.push_back(a);
}
else {
while(dp.size() > 0 && !(a < dp[0] && dp[0] >= grt))
dp.erase(dp.begin());
dp.push_back(a);
}
if(dp.size() == 1)
grt = 0;
else
grt = max(grt, a);
maxSize = max(maxSize, (int)dp.size());
}
dp.clear();
grt = 0;
for(int i = n - 1; i >= 0; i--) {
if(dp.size() == 0) {
dp.push_back(a);
}
else {
while(dp.size() > 0 && !(a < dp[0] && dp[0] >= grt))
dp.erase(dp.begin());
dp.push_back(a);
}
if(dp.size() == 1)
grt = 0;
else
grt = max(grt, a);
maxSize = max(maxSize, (int)dp.size());
}
cout
Подробнее здесь: https://stackoverflow.com/questions/796 ... om-cses-fi
