합창대형

제목 링크:https://www.luogu.org/problemnew/solution/P1091
사고방식: 최장 체증 서열(dp1[i]은 i 위치로 끝나는 LIS를 표시하고, 최장 체감 서열(dp2[i]은 i 위치로 시작하는 LDS(최장 체감 서열)를 다시 한 번 구한다. PS: 뒤에서 앞으로의 최장 체증 서열에 해당한다.정답은 렌1+렌2-1이다.
먼저 제 멍청한 코드(n^2logn)가 다음 코드를 썼습니다. 이 코드는 제가 LIS에 대한 이해가 부족합니다. 저는 각 위치의 i에 대해 [0,i]의 LIS를 구하고 [i,n-1]의 LDS를 다시 한 번 구한 다음len1+len2-1을 구합니다.

#include 
#include 

using namespace std;

const int maxn=200;

int a[maxn],dp1[maxn],dp2[maxn],b[maxn];

int mfind(int left,int right,int x,int ta) {
    int mid;
    if((ta&&b[right]x))
       return right+1;
    if(ta)
    {
       while(left=x)right=mid;
       }	
    }
    else  {
       while(leftx)left=mid+1;
       	 else if(b[mid]<=x)right=mid;
       	 //cout <> n;
    for(int i=0;i> a[i];
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    int ans=0;
    for(int i=1;i

수정 후 n^2 복잡도 코드: (위에 nlogn의 LIS가 적혀 있기 때문에 (정확하게 사용하지 않았지만) 더 이상 쓰지 않습니다)

#include 
#include 

using namespace std;

const int maxn=200;

int a[maxn],dp1[maxn],dp2[maxn],b[maxn];



int main() {
	int n;
	cin >> n;
	for(int i=0;i> a[i];
    for(int i=0;ia[i])dp1[j]=max(dp1[j],dp1[i]+1);
    for(int i=n-1;i>0;i--)
      for(int j=i-1;j>=0;j--)
      	  if(a[j]>a[i])dp2[j]=max(dp2[j],dp2[i]+1);
    int ans=0;
    for(int i=0;i