dp之最大和，m段最大和以及最大子矩阵

系统管理员 2022-09-20 09:26 156阅读 0赞

前一段时间因为要讲课学习了dp系列算法，学习了很多东西，给大一菜鸟讲了这个系列的算法，当时没有记录，前几天拿起来发现有点忘记了，所以在这里记录一下，最大和系列算法。

首先子串和 [http://acm.nyist.net/JudgeOnline/problem.php?pid=44][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\n",max);
        }
    }

下来是m段和、 [http://acm.nyist.net/JudgeOnline/problem.php?pid=742][http_acm.nyist.net_JudgeOnline_problem.php_pid_742] 就是把一个串分成m段的最大和。

状态转移方程为dp \[ i \] \[ j \] =max( max( dp\[i-1\]\[ t \] ),dp \[ i \] \[ j-1 \] ) + a\[ j \] ,dp \[ i \]\[ j \]表示串中前 j 个数分成 i 段的最大和，运用dp的思想进行分析的话，转化成最优子结构，即当前的状态由前一状态推得，假如让当前的a\[ j \] 自成一段，即前面的一段取能够取得的最大值，然后和自成一段的 a \[ j \]相加，则为max( dp\[i-1\]\[ t \] ) \+ a\[ j \] ，假如要和前面的前一个放到一起成为一段的话，就是dp \[ i \] \[ j-1 \] ) + a\[ j \] ，其实还是很好理解的。

实现的话，二维数组可以简化成一维数组，即用一层循环代替分段，然后用一个数组表示前一状况的最大值，然后直接运用前面的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\n",sum);
        }
        return 0;
    }

最后是最大子矩阵，运用的就是最大和+枚举+矩阵压缩[http://acm.nyist.net/JudgeOnline/problem.php?pid=104][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\n",m);
            memset(map,0,sizeof(map));
        }
        return 0;
    }

[http_acm.nyist.net_JudgeOnline_problem.php_pid_44]: http://acm.nyist.net/JudgeOnline/problem.php?pid=44
[http_acm.nyist.net_JudgeOnline_problem.php_pid_742]: http://acm.nyist.net/JudgeOnline/problem.php?pid=742
[http_acm.nyist.net_JudgeOnline_problem.php_pid_104]: http://acm.nyist.net/JudgeOnline/problem.php?pid=104