dp 의 최대 합,m 단 최대 및 최대 서브 매트릭스

얼마 전에 강 의 를 해 야 하기 때문에 dp 시리즈 알고리즘 을 배 웠 고 많은 것 을 배 웠 습 니 다.큰 새 에 게 이 시리즈 의 알고리즘 을 알려 주 었 습 니 다.그 때 는 기록 이 없 었 습 니 다.며칠 전에 들 어 보 니 약간 잊 어 버 렸 습 니 다.그래서 여기 서'최대 와 시리즈 알고리즘'을 기록 하 겠 습 니 다.
우선 하위 꼬치 와... http://acm.nyist.net/JudgeOnline/problem.php?pid=44
매우 간단 하 다.바로 하나의 상태 전이 방정식 이다.구 한 마지막 하 나 는 가장 큰 것 이 아니 라 그 중에서 가장 큰 숫자 가 가장 큰 것 임 을 명심 하 라.

dp[i]=Max((dp[i-1]+a[i]),a[i]);

 
#include <cstdio>
#define Max(a,b) a>b?a:b
int a[1000010],dp[1000010];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%d",&a[0]);
        int max=a[0];dp[0]=a[0];
        for(int i=1;i<n;i++)
        {
            scanf("%d",&a[i]);
            dp[i]=Max((dp[i-1]+a[i]),a[i]);
            if(dp[i]>max)
                max=dp[i];
        }
        printf("%d
",max);
    }
}
        

내 려 오 면 m 단 과...http://acm.nyist.net/JudgeOnline/problem.php?pid=742   한 꼬치 를 m 단의 최대 합 으로 나 누 는 것 이다.
상태 전이 방정식 은 dp[i][j]=max(dp[i-1][t]),dp[i][j-1]+a[j],dp[i][j][j]는 문자열 의 앞 j 개 수 를 i 세그먼트 의 최대 와 나 누 어 dp 의 사상 으로 분석 하면 가장 좋 은 서브 구조 로 전환 된다.즉,현재 의 상 태 는 앞의 상태 에서 추정 된다.만약 에 현재 의 a[j]를 한 단락 으로 만 들 면 앞의 단락 에서 얻 을 수 있 는 최대 치 를 취한 다.그리고 스스로 한 단락 을 이 루 는 a[j]와 더 하면 max(dp[i-1][t]+a[j]입 니 다.앞의 것 과 함께 한 단락 이 되 려 면 dp[i][j-1])+a[j]입 니 다.사실은 잘 이해 합 니 다.
이 를 실현 하면 2 차원 배열 은 1 차원 배열 로 간략화 할 수 있다.즉,1 층 순환 으로 세그먼트 를 대체 한 다음 에 한 배열 로 이전 상황 의 최대 치 를 표시 한 다음 에 앞의 dp 방정식 을 직접 활용 하면 된다.코드:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e6+5;
const int MIN = -(1<<30);
int a[N];
int dp[N],pre[N];
int main()
{
    int t,m,n,i,j,k;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        scanf("%d%d",&m,&n);
        for(i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        int sum;
        for(i = 1; i <= m; i++)
        {
            sum =  MIN;
            for(j = i; j <=n; j++)
            {
                dp[j] = max(dp[j-1],pre[j-1]) + a[j];
                pre[j-1] = sum;
                sum = max(dp[j],sum);
            }
            pre[j-1] = sum;
        }
        printf("%d
",sum);
    }
    return 0;
}

마지막 으로 가장 큰 서브 매트릭스 입 니 다.가장 큰 것 과+매 거 진+매트릭스 압축 을 사용 합 니 다.http://acm.nyist.net/JudgeOnline/problem.php?pid=104
사실은 입력 할 때 각 줄 의 아래 수 를 아래로 구하 고 이 열 에 있 는 모든 수의 합 을 표시 한 다음 에 시작 줄 과 끝 줄 을 매 거 하여 최대 와 기 존 결 과 를 구 하 는 것 을 판단 하 는 것 이다.
코드:

#include <stdio.h>
#include <string.h>
int map[102][102];
int main()
{
    int i,j,k,m,t,r,c,max,temp,cc=0;
    scanf("%d",&t);
    while(t--)
    {
        cc++;
        scanf("%d%d",&r,&c);
        for(i=1; i<=r; i++)
        {
            for(j=0; j<c; j++)
            {
                scanf("%d",&map[i][j]);
                map[i][j]=map[i][j]+map[i-1][j];
            }
        }
        for(i=1,m=map[1][0]; i<=r; i++)
            for(j=i; j<=r; j++)
            {
                for(k=max=0; k<c; k++)
                {
                    temp=map[j][k]-map[i-1][k];
                    max=(max>=0?max:0)+temp;
                    m=max>m?max:m;
                }
            }
        printf("%d
",m);
        memset(map,0,sizeof(map));
    }
    return 0;
}