CodeForces 547 B (단조 창고)
3192 단어 단조 로 운 창고-----DP-----데이터 구조
n 개의 요소 가 있 는 시퀀스 입 니 다. 연속 l 개의 요소 가 없 는 최소 값 은 이 문자열 의 strength 값 입 니 다. 모든 연속 l 개의 요소 의 strength 가 최대 값 입 니 다.
분석 하 다.
a [i] 만약 에 그 열 에 있 는 strength 값 이 라면 반드시 최소 값 이 고 앞으로 와 뒤로 그 첫 번 째 위치 l, r 보다 작은 위 치 를 찾 습 니 다. 분명히 [l + 1, r + 1] 구간 의 strength 는 a [i] 와 같 습 니 다.len (len = r - l + 1) 길이 의 strength 를 업데이트 할 수 있 습 니 다.그리고 길이 가 i 인 strength 값 은 길이 가 (i - 1) 인 strength 값 보다 크 지 않 습 니 다.
const int maxn = 2e5 + 10;
int a[maxn];
int ans[maxn];
int pre[maxn];
int nxt[maxn];
int n;
int main(int argc, const char * argv[])
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
// ios::sync_with_stdio(false);
// cout.sync_with_stdio(false);
// cin.sync_with_stdio(false);
cin >> n;
Rep(i, 1, n) scanf("%d", &a[i]);
vector<int> st;
Rep(i, 1, n) {
while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
st.empty() ? pre[i] = 0 : pre[i] = st.back();
st.push_back(i);
}
st.clear();
Rrep(i, n, 1) {
while(!st.empty() && a[st.back()] >= a[i]) st.pop_back();
st.empty() ? nxt[i] = n + 1 : nxt[i] = st.back();
st.push_back(i);
}
Rep(i, 1, n) {
int l = pre[i] + 1;
int r = nxt[i] - 1;
int len = r - l + 1;
ans[len] = max(ans[len], a[i]);
}
Rrep(i, n, 1) ans[i - 1] = max(ans[i - 1], ans[i]);
Rep(i, 1, n) printf("%d%c", ans[i], i == n ? '
' : ' ');
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POSJ - 2559 - Histogram - 단조 로 운 창고 에서 가장 큰 사각형소박 한 방법 은 모든 i 의 높이 를 매 거 하 는 것 이다. 사각형 의 폭 을 위해 양쪽 으로 가장 긴 사각형 을 찾 을 수 있 습 니 다. 모든 답 을 비교 해서 가장 큰 ans 를 얻 었 습 니 다. 물론 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
