BZOJ 1046 HAOI 2007 상승 시퀀스 DP
사고방식: 먼저 임의로 하나의 수조 f를 구하여 i부터 가장 긴 상승 서열의 길이를 나타낸다.그리고 욕심스럽게 뒤척이며 제자리에 놓을 수 있으면 놓으세요.
CODE:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 10010
#define INF 0x3f3f3f3f
using namespace std;
int src[MAX];
int f[MAX],max_length[MAX];
int cnt,asks;
bool cmp(int a,int b)
{
return src[a] > src[b];
}
int ans[MAX];
int main()
{
cin >> cnt;
for(int i = 1; i <= cnt; ++i)
scanf("%d",&src[i]);
for(int i = cnt; i; --i) {
int p = lower_bound(f + 1,f + cnt + 1,i,cmp) - f;
max_length[i] = max_length[f[p - 1]] + 1;
f[p] = i;
}
int length = 0;
while(f[length + 1]) ++length;
cin >> asks;
for(int x,i = 1; i <= asks; ++i) {
scanf("%d",&x);
if(x > length) puts("Impossible");
else {
int temp = x,last = -INF;
for(int i = 1; i <= cnt; ++i)
if(max_length[i] >= temp && src[i] > last) {
printf("%d",src[i]);
last = src[i];
--temp;
if(temp) putchar(' ');
else {
puts("");
break;
}
}
}
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
