hdu 1024 Max Sum Plus Plus(dp)

아이디어:
처음에는 정말 생각이 없어서 다른 사람을 보면 알 수 있다.
pp[i][j]는 전 j 개수가 i단으로 나뉘어 얻을 수 있는 최대 값을 표시하고 i단은 j 개의 그 요소인 a[j]를 포함한다. a수조는 원래 저장된 수의 수조를 표시한다.
dp[i][j]는 두 가지 상황을 얻을 수 있는데,
첫째: j번째 요소와 함께 i단의 끝, 즉 dp[i][j-1]+a[j]에 놓으면 dp[i][j]를 얻을 수 있다.
두 번째: j번째 원소가 단독으로 한 단락이 되면 앞의 j-1개 원소와 i-1단락으로 나누어 얻을 수 있는 최대치를 더한 다음에 dp[i][j], 즉max(dp[i-1[k]+a[j])(0이상은 이 dp 사고방식의 정수이다. 마지막 원소가 한 단락을 이루는 것이 가장 중요한 부분이다. 한 단락을 이루지 않는 모든 원소가 첫 번째 점에 포함된다. 즉, 첫 번째 원소는 한 단락을 이루고 나서야 긴 단락이 생기기 때문에 이 dp사로가 성립되었다.
상태 전환 방정식은 다음과 같습니다.
dp[i][j] = max(dp[i][j-1] + a[j], max(dp[i-1][k] + a[j])) (0

for( i = 1; i <= m; ++i){
for( j = i; j <= n; ++j){
dp[j] = dp[j-1] + a[j];
for(int r = 1; r < j; ++r){
dp[j] = max(dp[j],dp[r] + a[j]);
}
}
}

이렇게 보면 거의 문제가 해결된 것 같고 사고방식이 정확하며 코드는 문제없을 것이다.
그러나 제목의 j는 매우 크고 백만 등급에 달할 것이다. 그러면 i가 조금만 크면 MLE를 할 수 있고 TLE도 할 수 있기 때문에 시공 문제를 해결할 필요가 있다.
우리 계속 보면,
우리가 매번 dp를 순환할 때, 그 전후와 관련된 원소는 무엇입니까? 이것은 dp의 공간을 간소화하는 기본점입니다.
앞에서 i-1단으로 나뉘어진 결과와만 관련이 있다는 것을 알 수 있기 때문에 우리는 두 가지 방법으로 간소화할 수 있다.
첫 번째는 앞뒤 두 상태를 보존하면 공간 1차는 2로 고정되고 먹을 수 있다.
두 번째: 스크롤 수조이다. 스크롤 수조는 dp의 대표적인 공간 축소 방법이다. 왜냐하면 우리는 매번 방금 사용한 데이터를 덮어쓰기 때문에 우리는 1차원만 사용하면 실현할 수 있다.
이곳에 와서 우리는 공간의 문제를 해결했지만 시간의 문제는 여전히 해결되지 않았다.
우리는 max(dp[i-1][k]+a[j])(0그러면 이 문제를 어떻게 해결해야 하는가? 우리는 스크롤 그룹의 업데이트에서 스크롤 그룹의 유사한 원리를 발견할 수 있다. 우리는 스크롤 그룹의 유사 원리를 이용하여 이전 k개의 요소를 전문적으로 저장하여 i단의 요소의 최대치를 구성할 수 있다.
즉 mx[i][j]는 앞 1-j개 원소의 구성 i단의 최대치를 나타낸다. 즉max(dp[i-1][k]+a[j])(0이 때 우리는 스크롤 그룹을 사용하여 1차원 mx[j]로 만들 수 있다. 그러면 우리는 스크롤 그룹의 업데이트와 함께 mx의 값을 업데이트할 수 있다.
즉 하나의 mmax로 전 mx[i][j]를 저장한 다음에 그 값으로 다음 mx[j]의 값을 업데이트하면 1차원을 줄일 수 있다.

for( i = 1; i <= m; ++i){
    mmax = -INF;
    for(  j = i; j <= n; ++j){
         dp[j] = max(dp[j-1] + a[j], mx[j-1] + a[j]);
         mx[j-1] = mmax;
         mmax = max(mmax,dp[j]);
   }
}

매번 업데이트할 때마다 mx의 값을 업데이트합니다.
이 시공은 어느 정도 해결되었습니다. 859ms를 제출합니다...

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 1000010;
const int N = 100010;
const int INF = 0x7fffffff;

int a[MAX_], mx[MAX_] ,dp[MAX_];


int main(){
	int n, m, mmax, i, j;
	while(~scanf("%d%d",&m,&n)){
        for( i = 1; i <= n; ++i){
            scanf("%d",&a[i]);
            dp[i] = mx[i] = 0;
        }
        dp[0] = mx[0] = 0;
        for( i = 1; i <= m; ++i){
            mmax = -INF;
            for(  j = i; j <= n; ++j){
                /*dp[j] = dp[j-1] + a[j];
                for(int r = 1; r < j; ++r){
                    dp[j] = max(dp[j],dp[r] + a[j]);
                }*/
                dp[j] = max(dp[j-1] + a[j], mx[j-1] + a[j]);
                mx[j-1] = mmax;
                mmax = max(mmax,dp[j]);
            }
            //mx[n] = mmax;
        }
        printf("%d
",mmax);
	}
	return 0;
}

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

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

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

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

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

hdu 1024 Max Sum Plus Plus(dp)

좋은 웹페이지 즐겨찾기