[문제풀이] NOIP 보급팀 로곡P1020 미사일 요격

3459 단어 dp탐욕스럽다

NOIP 보급팀 미사일 요격

  • NOIP 보급팀 미사일 요격
  • 시험점
  • 제의
  • 사고방식
  • 코드
  • 시험 장소

  • 욕심
  • DP

  • 제목의 뜻


    로곡 링크는 몇 가지 배열된 수가 있는데, 가장 긴 불상승자 서열의 길이와 가장 적은 가장 긴 불상승자 서열의 개수를 구한다

    사고의 방향


    첫 번째 질문, WOC 최장 상승 서열!DP타격의 두 번째 꼬마를 찍어서 처음에 DP를 쓰려고 했는데 NOIP 정신을 발휘했어. 데이터가 이렇게 작아?직접 매거하면 되지만, 어떤 방안들은 어떻게 결정합니까?만약 네가 이 미사일을 칠 수 있고 네가 고도가 가장 낮은 사람이라면 네가 직접 그를 때려라. 그렇지 않으면 기회가 없을 것이다.

    코드

    #include
    #include
    using namespace std;
    
    int a[101],cnt;
    int dp[101];
    int ans;
    
    int sy[101];
    
    int main()
    {
        for(int i=1;i<=100;++i) dp[i]=1;
        dp[1]=1;
        cnt=1;
        while(cin>>a[cnt]) ++cnt;
        cnt--;
        for(int i=1;ifor(int j=i+1;j<=cnt;++j)
            {
                if(a[i]>a[j])
                {
                    dp[j]=max(dp[i]+1,dp[j]);
                }
            }
        }
        for(int i=1;i<=cnt;++i) ans=max(ans,dp[i]);
        printf("%d
    "
    ,ans); int tot=1; int cun,shortest; sy[1]=a[1]; for(int i=2;i<=cnt;++i) { shortest=99999; cun=-1; for(int j=1;j<=tot;++j) { if(sy[j]>a[i]) { if(sy[j]if(cun==-1) { sy[++tot]=a[i]; } else { sy[cun]=a[i]; } } printf("%d
    "
    ,tot); }

    이 문제는 그래도 좀 어려워서 좋은 문제라고 할 수 있겠지(하지만 사고방식은 틀림없이 매우 간단할 것이다)

    좋은 웹페이지 즐겨찾기