poj-1836
//380K 79MS G++
#include <cstdio>
#include <cstring>
using namespace std;
double soldiers[1005];
struct soldierInfo{
double prevHeight;
int num;
};
typedef struct soldierInfo soldierInfo;
soldierInfo aux[1005];
int tmpSolider[1002];
int soldierNum;
int lengthMAX;
#define INF 999999
// void solve() {
// int beginSoldierId = 1;
// lengthMAX = -INF;
// memset(aux, 0, sizeof(aux));
// while(1) {
// if (beginSoldierId > soldierNum){
// break;
// }
// int thisTimeSoldierNum = 0;
// if (aux[beginSoldierId].num == 0) {
// printf("C %d", beginSoldierId);
// int i = 0;
// aux[beginSoldierId].num = 1;
// aux[beginSoldierId].prev
// tmpSolider[thisTimeSoldierNum++] = beginSoldierId;
// for (i = beginSoldierId; i <= soldierNum; i++) {
// if (soldiers[i] < soldiers[beginSoldierId]) {
// if (aux[i].num > 0) {
// for (int i = 0; i < thisTimeSoldierNum; i++) {
// int soldierId = tmpSolider[i];
// aux[soldierId].num = thisTimeSoldierNum - i + aux[i].num;
// }
// break;
// } else {
// tmpSolider[thisTimeSoldierNum++] = i;
// // thisTimeSoldierNum++;
// }
// }
// }
// if (i == soldierNum + 1) {
// printf("B %d
", beginSoldierId);
// for (i = 0; i < thisTimeSoldierNum; i++) {
// printf("V %d %d
", tmpSolider[i], thisTimeSoldierNum - i);
// int soldierId = tmpSolider[i];
// aux[soldierId].num = thisTimeSoldierNum - i;
// }
// }
// }
// printf("%d %d
", aux[beginSoldierId].num, beginSoldierId);
// lengthMAX = lengthMAX > aux[beginSoldierId].num ? lengthMAX : aux[beginSoldierId].num;
// beginSoldierId++;
// }
// printf("%d
", soldierNum - lengthMAX);
// }
int DP[1005];
int DP2[1005];
int solve2() {
memset(DP, 0, sizeof(DP));
memset(DP2, 0, sizeof(DP2));
// jiang
for (int i = soldierNum; i >= 1; i--) {
if (i == soldierNum) {
DP[i] = 1;
} else {
int MAXLEN = 1;
for (int j = i+1; j <= soldierNum; j++) {
// printf("%d %d %lf %lf
", i, j, soldiers[i], soldiers[j]);
if (soldiers[j] < soldiers[i]) {
int length = DP[j] + 1;
MAXLEN = MAXLEN > length ? MAXLEN: length;
}
}
DP[i] = MAXLEN;
}
// printf(" < %d %d
", DP[i], i);
}
//sheng
for (int i = 1; i <= soldierNum; i++) {
if (i == 1) {
DP2[i] = 1;
} else {
int MAXLEN2 = 1;
for (int j = 1; j <= i-1; j++) {
// printf("%d %d %lf %lf
", i, j, soldiers[i], soldiers[j]);
if (soldiers[j] < soldiers[i]) {
int length = DP2[j] + 1;
MAXLEN2 = MAXLEN2 > length ? MAXLEN2: length;
}
}
DP2[i] = MAXLEN2;
}
// printf(" > %d %d
", DP2[i], i);
}
int MAXLEN3 = DP2[soldierNum] > DP[1] ? DP2[soldierNum] : DP[1];
// printf("%d
", MAXLEN3);
if (soldierNum >= 3) {
for (int split = 2; split <= soldierNum-1; split++) {
// memset(DP, 0, sizeof(DP));
// memset(DP2, 0, sizeof(DP2));
// //jiang
// int maxlength1 = 0;
// int jiangBegin = split;
// for (int i = soldierNum; i >= split + 1; i--) {
// if (soldiers[i] < soldiers[split]) {
// if (i == soldierNum) {
// DP[i] = 1;
// } else {
// int MAXLEN = 1;
// for (int j = i+1; j <= soldierNum; j++) {
// // printf("%d %d %lf %lf
", i, j, soldiers[i], soldiers[j]);
// if ((soldiers[j] < soldiers[i]) &&
// (soldiers[j] < soldiers[split]) &&
// (soldiers[i] < soldiers[split])) {
// int length = DP[j] + 1;
// MAXLEN = MAXLEN > length ? MAXLEN: length;
// }
// }
// DP[i] = MAXLEN;
// }
// }
// if (maxlength1 < DP[i]) {
// maxlength1 = DP[i];
// jiangBegin = i;
// }
// // maxlength1 = DP[i] > maxlength1 ? DP[i]: maxlength1;
// // printf(" > %d %d
", DP[i], i);
// }
// //sheng
// int maxlength2 = 0;
// int shengEnd = split;
// for (int i = 1; i <= split-1; i++) {
// if (soldiers[i] < soldiers[split]) {
// if (i == 1) {
// DP2[i] = 1;
// } else {
// int MAXLEN2 = 1;
// for (int j = 1; j <= i-1; j++) {
// // printf("%d %d %lf %lf
", i, j, soldiers[i], soldiers[j]);
// if ((soldiers[j] < soldiers[i]) &&
// (soldiers[j] < soldiers[split]) &&
// (soldiers[i] < soldiers[split])) {
// int length = DP2[j] + 1;
// MAXLEN2 = MAXLEN2 > length ? MAXLEN2: length;
// }
// }
// DP2[i] = MAXLEN2;
// }
// }
// if (maxlength2 < DP2[i]) {
// maxlength2 = DP2[i];
// shengEnd = i;
// }
// // maxlength2 = DP2[i] > maxlength2 ? DP2[i]: maxlength2;
// // printf(" < %d %d
", DP2[i], i);
// }
int maxlength1 = 0;
int maxlength2 = 0;
int jiangBegin = split;
int shengEnd = split;
//sheng
for (int i = 1; i <= split-1; i++) {
if (soldiers[split] > soldiers[i]) {
if (maxlength1 < DP2[i]) {
shengEnd = i;
maxlength1 = DP2[i];
}
}
}
//jiang
for (int i =soldierNum; i >= split+1; i--) {
if (soldiers[split] > soldiers[i]) {
if (maxlength2 < DP[i]) {
jiangBegin = i;
maxlength2 = DP[i];
}
}
}
int heightEqualNum = 0;
int heightEqualNum1 = 0;
for (int i = shengEnd + 1; i <= jiangBegin -1; i++) {
if (soldiers[i] == soldiers[split]) {
heightEqualNum++;
if (heightEqualNum >=2) {
heightEqualNum1 = 1;
break;
}
}
}
// printf("%d %d
", shengEnd, jiangBegin);
// printf("%d %d %d %d
", split, maxlength1, maxlength2, heightEqualNum);
int tmpMAXLEN = maxlength1 + maxlength2 + 1 + heightEqualNum1;
MAXLEN3 = tmpMAXLEN > MAXLEN3 ? tmpMAXLEN: MAXLEN3;
// printf("%d %d
", split, MAXLEN3);
}
}
printf("%d
", soldierNum - MAXLEN3);
}
int main() {
while(scanf("%d", &soldierNum) !=EOF) {
for (int i = 1; i <= soldierNum; i++) {
scanf("%lf", &soldiers[i]);
}
// solve();
solve2();
}
}지금은 DP에 대해 조금 서툴러서 기본적인 최장 점증 서열의 구법도 잊어버렸다.
이 문제는 DP 자체가 아니라 세부적인 처리에 있어서 문제가 까다롭다.
대열을 조정한 후 모든 병사들은 적어도 가장 왼쪽이나 가장 오른쪽의 사람을 볼 수 있다. 주의, 예, 그리고 좌우 양쪽을 볼 수 있다. 그러면 단순히 최장 점증/점감 서열을 구하는 것이 아니다.
중간에서 가장 높은 병사를 한 명 찾아서 양쪽으로 줄일 수 있기 때문에, 이것은 가장 긴 점증 서열과 가장 짧은 점증 서열의 조합이 되었다.
예를 들어 대기열 S의 경우
4
3 4 5 1 2 5 4 33, 4, 5, 4, 3, 가장 높은 병사 5가 중간에 있고 왼쪽과 오른쪽으로 줄어듭니다. 하지만 주의하세요. 이게 최선이 아니에요!제목은 맨 왼쪽/맨 오른쪽만 보여야 하기 때문에 이렇게 줄을 설 수 있습니다.
3 4 5 5 4 3,
이렇게 줄을 서면 키가 5인 두 명의 병사가 중간에 있는데 각각 가장 왼쪽/오른쪽을 볼 수 있어 가장 좋은 대열(가장 긴 대열)이다.
이렇게 해서 이런 요소를 감안하면 본 문제는 좀 번거로워진다.
먼저 전체 수조에 대해 최장 증가/감소 서열을 구하고,
적절한 DP 배열:
DP1[]은 증가에 대응하고 DP1[i]은 S[i]로 끝나는 증가된 시퀀스의 최대 길이를 나타냅니다.
DP2[]는 감소에 대응하고 DP2[i]는 S[i]로 시작하는 (S[N]로 끝나는) 감소 시퀀스의 최대 길이를 나타냅니다.
두 방법 중 가장 긴 시퀀스인 LX LY를 얻을 수 있습니다.
그리고 각 병사를 일일이 열거하여 이 병사가 가장 마지막 대열의 중간 최고자를 고려하여 대열의 길이를 구한다.
만약에 병사 i를 중간 최고자로 한다면 왼쪽의 최장 체증 서열과 오른쪽의 최장 체감 서열을 요구해야 한다. 주의해야 할 것은 이곳의 체증 서열의 최대치는 S[i]를 넘을 수 없다. 마찬가지로 체감 서열의 최대치도 S[i]를 넘을 수 없다. 나는 여기서 헷갈리고 체증과 체감을 다시 한 번 구했다. 사실은 전혀 사용하지 않는다. 그래서 이전의 DP1과 DP2는 이미 이 정보를 포함했다.
S[i]의 왼쪽에 가장 큰 DP1[j]만 필요하고 S[j]
이 같은 키의 병사가 있다면 제목의 수요에 부합되면 마지막 대열에서 i와 바짝 붙어 있을 수밖에 없다.
i 왼쪽의 최장 체증 서열의 끝 위치는left이고 i 오른쪽의 최장 체감 서열의 시작 위치는right,
그렇다면 조건에 맞는 같은 키의 병사m가 있다면 분포는 다음과 같을 수밖에 없다.
....left.....m.....i.....right 또는...left....i....m.....right,
이것을 통해 병사 m가 있는지 확인할 수 있습니다.left+1에서right-1까지의 서열을 두루 돌아다닐 수 있습니다.>1(i 자체를 포함하기 때문에 >1은 i를 제외한 다른 같은 키의 병사가 있음을 나타냅니다.)i와 같은 키의 병사가 있다면 m가 존재하지만 한 m만 선택할 수 있습니다.(두 m가 있으면 문제를 만족시키지 못합니다)
이 단계에 이르렀을 때 기본적으로 완성되었지만 세부 사항이 하나 더 있습니다. 왼쪽/오른쪽의 최장 증가/감소 서열에 같은 길이의 최장 서열이 여러 개 있다면left와right는left최소,right최대의 서열을 선택해야 합니다.
이렇게 하면 m를 선택하는 서열이 가장 길다는 것을 보장할 수 있다. 만약 m가 존재한다면 반드시 찾을 수 있을 것이다.그리고 i가 가장 왼쪽과 가장 오른쪽에 있는 상황을 고려했습니다. 이럴 때 왼쪽/오른쪽에 한 쪽은 고려하지 않아도 됩니다.
왼쪽 최장 체증 서열 길이 L1과 오른쪽 최장 체감 서열 길이 L2의 초기값이 0(예를 들어 569, 6을 i로 선택하면 왼쪽, 오른쪽에 i보다 작은 체증/체감 서열이 없다)
마지막 길이는 L1 + L2 + 1 (m이 존재하면) + 1 (i 자체가 최종 서열의 일부분)
이전 LX LY와 각 점의 마지막 길이를 결합하면 가장 긴 시퀀스가 최종 시퀀스입니다.
열거하고자 하는 인원수는 원래 대열의 길이를 최종 서열의 길이를 줄이면 된다.
이 문제는 세부적인 것을 매우 고찰하니 앞으로 이런 문제를 많이 연습해야 한다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
