[noip2013] 꽃장인DP||욕심

6181 단어 dp탐욕스럽다noip

제목 설명Description


화공의 동채에 한 줄의 꽃을 심었는데, 꽃마다 모두 자신의 높이가 있다.꽃은 자랄수록 커지고 비좁아진다.동동은 이 줄의 일부 꽃을 옮기고 나머지는 제자리에 남겨 남은 꽃이 자랄 수 있는 공간을 마련하기로 했다. 또한 동동은 남은 꽃이 색다르게 배열되기를 바란다.구체적으로 말하면 동채의 꽃의 높이는 일렬 정수h 로 볼 수 있다1, h_2, … , h_n.일부 꽃이 옮겨진 후 남은 꽃의 높이는 순서대로 g1, g_2, … , g_m, 동동은 다음 두 가지 조건 중 최소한 하나가 충족되기를 희망한다. 조건 A: 모든 1 g_2i-1 및 g2i > g_2i+1; 조건 B: 모든 1의 경우 < i < m/2, g2i < g_2i-1 및 g2i < g_2i+1. 위의 두 가지 조건은 m=1시에 동시에 만족하고 m>1시에 최대 하나가 만족할 수 있음을 주의하세요.실례합니다만, 동은 최대 몇 그루의 꽃을 제자리에 남겨 둘 수 있습니까?

설명 입력 Input Description


입력한 첫 번째 행에는 시작 시 꽃의 포기 수를 나타내는 정수 n이 포함됩니다.두 번째 행에는 h 순으로 n개의 정수가 포함됩니다.1, h_2,… , h_n, 꽃마다 높이를 나타낸다.

출력 설명 Output Description


제자리에 남을 수 있는 꽃의 주수를 나타내는 정수 m를 포함하는 줄을 출력합니다.

샘플 Sample Input 입력


5 5 3 2 1 2

샘플 출력 Sample Output


3

데이터 범위 및 프롬프트 Data Size & Hint


20%의 데이터에 대해 n≤10;30%의 데이터에 대해 n≤25;데이터 70%의 경우 n≤1000, 0≤hi ≤ 1000; 100% 데이터의 경우 1≤n≤100000, 0≤hi≤1000000, 모든 hi 무작위 생성, 모든 무작위 수는 특정 구간 내의 고른 분포에 복종한다.
한눈에 DP를 봤는데 요 며칠 마침 DP를 배웠어요. 그래서 문제를 보고 n^2의 알고리즘을 쳤어요. A는 8개 점을 찍었어요.
dp 코드:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int size=100010;

int num[size];
int dp1[size][2],dp2[size][2];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        dp1[i][0]=dp1[i][1]=1;
        dp2[i][0]=dp2[i][1]=1;
        for(int j=1;j<i;j++)
        {
            if(num[j]<num[i])
            {
                dp2[i][0]=max(dp2[i][0],dp2[j][1]+1);
                dp1[i][1]=max(dp1[i][1],dp1[j][0]+1);
            }
            if(num[j]>num[i])
            {
                dp1[i][0]=max(dp1[i][0],dp1[j][1]+1);
                dp2[i][1]=max(dp2[i][1],dp2[j][0]+1);       
            }
        }
        ans=max(ans,max( max(dp1[i][0],dp2[i][0]) , max(dp1[i][1],dp2[i][1]) ) );
    }
    printf("%d",ans);
    return 0;
}

문제풀이를 보니까 사실 욕심이 많아서...
우선, 연속적으로 상승하거나 하락하는 서브열을 가지고, 우리는 원소를 보존하면 된다.답은 전환점의 개수다.시작점 끝점 등 조그 포인트를 집계하여 출력하면 됩니다.
코드:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;


int main()
{
    int n,ans1=1,ans2=1;
    scanf("%d",&n);
    for(int i=1,last,x;i<=n;i++)
    {
        scanf("%d",&x);
        if(i==1) {last=x;continue;}
        if(last<x) {ans1=max(ans1,ans2+1);}
        if(last>x) {ans2=max(ans2,ans1+1);}
        last=x;
    }
    printf("%d",max(ans1,ans2));
    return 0;
}

ans1 표시: 현재 수는 종점이며 현재 상승 서열의 최대 길이입니다.ans2는 현재 수가 종점이며, 현재 순서가 내려갈 때의 최대 길이입니다.
단지 이전 숫자와 비교하면 돼, 전환점을 통계하면 돼.
UVA 10581 - Partitioning for fun and profit
WordPress에서 마이크로CMS로 보도를 옮길 때의 비망록

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage