글 읽기 - 11054 바이토닉 수열 다른분들 아이디어가궁굼합니다

sontg123 3년 전 1

더러운 코드로 통과 했습니다 좀더 깔끔하게 풀어보고싶어서 여러분들의 아이디어가 궁굼합니다

제 아이디어는

n번째 앞 에서의 증가수열과 n번째뒤에서의 감소수열의 최대개수를 합해서 -1했습니다 이중 가장 큰값을 저장해놓고 정답으로 냈구요

이렇게 하기위해서는 수열의 모든수를 기준으로 검사해야 하고 for(처음~끝) 까지 할때 앞 증가수열은 차근차근 하나씩 증가하니 할때마다 하나만 더해서 검사해주면 되는데 뒤에 감소수열은 처음부터 거의 전체를검사하여 만들어야하고 고민끝에 전체를 만들때 이를 chache로저장해놨다가 쓰는 방법으로했습니다 설명이 복잡한거처럼 코드도 드러워서 다른 아이디어가 궁굼합니다

#include <iostream>
#include <vector>
using namespace std;
class sub_sqeuence{
private:
    vector<int> up_chache;
    vector<int> dw_chache;
    vector<int> map;
    int N;
public:
    sub_sqeuence(int n):N(n){
        map.resize(n+1,0);
        dw_chache.resize(n+1,0);
    }
    void set_val(){
        for(int i=1;i<=N;i++)
            std::cin >> map[i];
        up_chache.push_back(map[1]);
        dw_chache[N]=1;
    }
    void DP(){
        if(N==1){
            std::cout <<1<<'\n';
            return ;
        }
        int tmp,max=0;
        for(int i=2;i<=N;i++){
            tmp=up_sq(i)+dw_sq(i)-1;
            if(tmp>max)
                max=tmp;
        }
       std::cout << max<<'\n';
        return ;
    };
    int up_sq(int n){
        if(n==1)
            return 1;
        if(map[n]>up_chache[up_chache.size()-1])
            up_chache.push_back(map[n]);
        else{
            for(int i=0;i<up_chache.size();i++)
                if(up_chache[i]>=map[n]){
                    up_chache[i]=map[n];
                    break;
                }
        }
        return up_chache.size();
    };
    int dw_sq(int n){
        if(n==N)
           return 1;
        else if(dw_chache[n]!=0)
            return dw_chache[n];
        
        vector<int> temp;
        temp.push_back(map[N]);
        for(int i=N-1;i>=n;i--){
            if(map[i]>temp[temp.size()-1]){
                temp.push_back(map[i]);
                dw_chache[i]=temp.size();
            }
            else{
                for(int j=0;j<temp.size();j++){
                    if(temp[j]>=map[i]){
                        temp[j]=map[i];
                        break;
                    }
                }
                dw_chache[i]=temp.size();
            }
        }
        return temp.size();  
    
    };

    void print_chache(){
        for(int i=0;i<dw_chache.size();i++)
            std::cout << dw_chache[i]<<' ';
        std::cout <<'\n';
    } 
};
int main(){
    int n;
    std::cin >> n;
    sub_sqeuence sq(n);
    sq.set_val();
    sq.DP();

    return 0;
}

playsworld16 3년 전 6

제 코드를 공유합니다. 아이디어는 같습니다.

감소수열의 경우, 수열을 뒤집으면 증가수열을 구하는 것과 같습니다.

upper[x] 는 0~x까지의 최장 증가수열의 길이,

lower[x] 는 x~끝까지의 최장 감소수열의 길이입니다.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    vector<int>base(n);
    for(auto& i : base) cin >> i;
    
    vector<int> upper(n+1);
    vector<int> lower(n+1);
    
    for (int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            if(base[j] < base[i]){
                upper[i] = max(upper[i], upper[j]);
            }
        }
        upper[i]++;
    }

    for(int i = n-1; i >= 0; i--){
        for (int j = n-1; j > i; j--){
            if (base[j]<base[i]){
                lower[i] = max(lower[i], lower[j]);
            }
        }
        lower[i]++;
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++){
        ans = max(ans, lower[i] + upper[i]);
    }
    
    cout << ans-1;
}

tmzbqm 3년 전 0

코드 잘 보고 갑니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11054 바이토닉 수열 다른분들 아이디어가궁굼합니다

sontg123 3년 전 1

playsworld16 3년 전 6

tmzbqm 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말