HDOJ-1087-Super Jumping! Jumping! Jumping! 문제풀이 보고서

단순 동적 기획 문제(이 문제는 이름이 참 길다.,,) 마치 내가 예전에 비슷한 최장 상승 서열의 문제를 본 것 같다.제목의 대의: 항저우전기에서 이런 바둑 게임이 있는데 바둑판에 기점과 종점이 있다. 기점과 종점 사이의 점은 숫자로 표시하여 이 점에 도착하면 얻을 수 있는 점수를 대표한다. 모든 사람은 기점에서 출발할 수 있고 매번 한 걸음 한 걸음 다음 점까지 가면 이 점의 점수를 얻을 수 있다.한 번에 여러 점을 뛰어넘을 수 있지만 전제는 이 점의 점수가 걸음 전의 점의 점수보다 높다는 것이다. 예를 들어 기점에서 종점까지(기점은 점수가 가장 작고 종점은 점수가 가장 크다).각 점의 점수를 주고 기점에서 종점에 도착한 후에 얻을 수 있는 최대 점수를 구하세요.
나의 문제풀이 사고방식: 우리는 dp[i]가 기점에서 i점에 도달했을 때 얻을 수 있는 가장 큰 점수라고 가정한다.num[i]는 i점의 점수이다. 그러면 문제를 통해 이 점의 상태 이동 공식이 dp[i]=max(dp[i],dp[x1]+num[i],...dp[xn]+num[i])라는 것을 쉽게 알 수 있다. 그 중에서 xn은 매 점의 점수가num[i]보다 크지 않고 i보다 앞의 점이다.우선 초기화하면 dp[i]=num[i]는 의심할 여지가 없다.그리고 상태 이동 방정식에 따라 답이 그중에서 가장 큰 dp임을 알 수 있다.
다음은 제 문제풀이 코드입니다.

#include 
#include 
#include 
#include 

using namespace std;

#define N 1111

int n;
int num[N];     //       
int dp[N];      //            

void Read();        //  

void DataProcess(); //  

int main()
{
    while (~scanf("%d", &n))
    {
        if (n == 0) break;
        Read();
        DataProcess();
    }
    return 0;
}

void Read()
{
    for (int i=1; i<=n; ++i)
    {
        scanf("%d", &num[i]);
        dp[i] = num[i];         //     
    }
    dp[0] = num[0] = 0;     //   ，    
    return;
}

void DataProcess()
{
    int ans = 0;
    for (int i=1; i<=n; ++i)
    {
        for (int j=i+1; j<=n; ++j)
        {
            if (num[j] > num[i])
            {
                dp[j] = max(dp[j], dp[i] + num[j]);
            }
        }
        ans = max(dp[i], ans);
    }
    printf("%d
", ans);
    return;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[문제풀이] BZOJ 1010 장난감 포장 Toy

dp[j]+(f[i]−f[j]−c)2≤dp[k]+(f[i]−f[j]−c)2 d p [ j ] + ( f [ i ] − f [ j ] − c ) 2 ≤ d p [ k ] + ( f [ i ] − f [ j ] − c ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDOJ-1087-Super Jumping! Jumping! Jumping! 문제풀이 보고서

좋은 웹페이지 즐겨찾기