HDU - 1024 Max Sum Plus Plus(dp)
사고방식: dp방정식을 비교적 간단하게 내놓을 수 있는 것은 어떤 dp[i][j]가 현재 i덩어리가 있다는 뜻이다. j개수에서 교차하지 않는 구간과 최대치가 있다면 dp[i][j]=max(dp[i][j-1]+a[j], dp[i-1][k]+a[j]) 중 0<=k<=j-1, 대개 dp[i][j]는 현재 이 단락에 a[j]를 추가하거나 앞에 있는 단락(j]에서 다시 시작할 수 있다.
그러나 데이터 n의 크기는 1e6이고 m은 모르기 때문에 2차원으로 켜면 mle가 될 수 있다. 그 다음에 n^3의 시간 복잡도는 T가 떨어진다. 스크롤 그룹은 위의 문제를 간단하게 해결할 수 있다. n^3의 시간 복잡도를 어떻게 최적화하는지 우리는 dp[i-1][k]+a[j]에서 우리가 원하는 것이 최대치라는 것을 알고 있다. 그러면 우리는 0에서 j-1까지의 최대치를 유지하면 된다.우리가 dp[j]를 계산할 때 유지하는 김에 코드를 봅시다.
#include
#include
#include
#define inf 0x7fffffff
const int maxn = 1e6+10;
using namespace std;
long long a[maxn],Mmax;
long long dp[maxn],MAX[maxn];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
memset(MAX,0,sizeof(MAX));
for(int i = 1 ; i <= m ; i++)
{
scanf("%lld",&a[i]);
}
dp[0] = 0 ;
MAX[0] = 0 ;
for(int i = 1 ; i <= n; i++)
{
Mmax = -inf;
for(int j = i ; j <= m; j++)
{
dp[j] = max(dp[j-1]+a[j] , MAX[j-1]+a[j]);
MAX[j-1] = Mmax;
Mmax= max(dp[j],Mmax);
}
}
printf("%lld
",Mmax);
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
