Max Sum Plus Plus HDU-1024
이 문제의 상태 이동 방정식 dp[i][j]=max(dp[i][j-1]+a[j],Max(dp[i][k]+a[j])).사고: DP를 처음 접한 후에 다른 사람의 문제 풀이 사고를 보고 그의 과정을 한참 생각했다.우선 한 단락의 서열을 구하는 최대 연속 서열로 간주한다. 얻을 수 있는 상태 이동 방정식은 dp[j]=max(0, dp[j-1])+a[j]이다.-현재 서열의 최대 연속 서열을 j까지 구하십시오.제목은 m조를 요구한다.주로 맥스[N+10], 수조의 사용, 맥스[N+10], 전 dp[j]의 최대치를 기록합니다.
#include
#include
#include
#include
using namespace std;
const int N=1000000;
const int inf=0x7f7f7f7f;
int dp[N+10],Max[N+10];
int a[N+10];
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
memset(Max,0,sizeof(Max));
int maxn;
for(int i=1;i<=m;i++)
{
maxn=-inf;
for(int j=i;j<=n;j++)
{
dp[j]=max(dp[j-1]+a[j],Max[j-1]+a[j]);
Max[j-1]=maxn;
maxn=max(maxn,dp[j]);
}
/*cout<
}
cout<return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 매 결점의 왼쪽 아이와 오른쪽 아이를 교환하여 ~2020.8.13~ 학습노트두 갈래 체인 시계를 두 갈래 나무의 저장 구조로 삼아 두 갈래 나무의 각 결점의 왼쪽 아이와 오른쪽 아이를 교환한다. 두 갈래 나무의 순서를 입력하십시오.알림: 두 갈래 나무의 순서 서열은 문자열입니다. 문자가'#...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.