Max Sum Plus Plus HDU-1024

Max Sum Plus Plus HDU-1024의 뜻: n개의 수를 주고 m개의 연속 서열을 찾아서 m개의 연속 서열을 최대(요구도 서열이 겹치지 않음), m조의 서열과 최대치를 출력합니다.
이 문제의 상태 이동 방정식 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;
} 

좋은 웹페이지 즐겨찾기