Codeforces gym 101291M(최장 교체 하위 시퀀스)【DP】
제목의 대의: 서열을 하나 드리겠습니다. 이 서열의 가장 긴 교체 서열을 구해 주십시오. 이른바 가장 긴 교체 서열이란 이 서열의 인접한 세 가지는 반드시 먼저 점차적으로 증가하고 다시 점차적으로 감소하거나 먼저 점차적으로 증가하고 다시 점차적으로 증가해야 합니다. 이렇게 교체해야 합니다.
문제 풀이 분석:
이것은 한 dp의 전형적인 문제에서 가장 긴 상승 서열을 구하는 것과 약간 비슷하다. 다른 것은 본 문제는 서열이 서로 인접한 두 항목이 교체하여 변환해야 하기 때문에 원래의 기초 위에서 약간의 변동을 하고 두 개의 dp수조로 각각 시작 상태가 점차적으로 증가하고 시작 상태가 점차적으로 줄어드는 상황을 기록한 다음에 dp의 짝수에 따라 이 단계가 점차적으로 증가하는지 감소하는지 판단한다.
#include
#include
int max(int a,int b){return a>b?a:b;}
int main(){
int arr[110];
int n;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&arr[i]);
}
int dp1[110],dp2[110];
for(int i=1;i<=n;i++){ //
dp1[i]=1,dp2[i]=1; //dp1[i] ,dp2[i]
}
for(int i=2;i<=n;i++){
for(int j=1;jdp1[i]){
dp1[i]=dp1[j]+1;
}
}
else{
if(arr[j]>arr[i]&&(dp1[j]+1)>dp1[i]){
dp1[i]=dp1[j]+1;
}
}
//dp2[]
if(dp2[j]%2==1){ // dp2[j] ，
if(arr[j]>arr[i]&&(dp2[j]+1)>dp2[i]){
dp2[i]=dp2[j]+1;
}
}
else{
if(arr[j]dp2[i]){
dp2[i]=dp2[j]+1;
}
}
}
}
int mx=-0x3f;
for(int i=1;i<=n;i++){
mx=max(max(mx,dp1[i]),dp2[i]);
}
printf("%d
",mx);
return 0;
}
전재 대상:https://www.cnblogs.com/00isok/p/9652395.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
