POJ 1050 To the Max 矩阵最大和的子数组:动态规划

刺骨的言语ヽ痛彻心扉 2023-06-15 14:24 3阅读 0赞

**将原来的矩阵直接改造成dp矩阵  
dp\[i\]\[j\] 表示以以a\[0\]\[0\]为左上角 a\[i\]\[j\]为右下角的矩阵之和**  
**所以一个O( n 4 n^\{4\} n4)的算法就比较容易写了**

**状态转移：**  
**表示（不包括）左上角( ii , jj )右下角(i , j)的子矩阵和**

ret = max(ret, a[i][j] + a[ii][jj] - a[i][jj] - a[ii][j]);

#include <iostream>
    #include <stdio.h>
    #include <limits.h>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    int a[101][101];
    int N;
    int ret = INT_MIN;
    
    void disp(){ 
        for(int i=0;i<N;i++){ 
            for(int j=0;j<N;j++){ 
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    int main()
    { 
    
        while(cin>>N){ 
            for(int i=0;i<N*N;i++){ 
                scanf("%d",&a[i/N][i%N]);
            }
            ret = INT_MIN;
            for(int i=1;i<N;i++){ 
                a[i][0] = a[i-1][0] + a[i][0];
                a[0][i] = a[0][i-1] + a[0][i];
            }
            for(int i=1;i<N;i++){ 
                for(int j=1;j<N;j++){ 
                    a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
                    ret = max(ret,a[i][j]);
                    //debug(i)
                    //debug(j)
                    for(int ii=0;ii<i;ii++){ 
                        ret = max(ret, a[i][j] -a[ii][j]);
                    }
                    for(int jj=0;j<j;jj++){ 
                        ret = max(ret, a[i][j] -a[i][jj]);
                    }
                    for(int ii=0;ii<=i;ii++){ 
                        for(int jj=0;jj<=j;jj++){ 
                            //debug(ii)
                            //debug(jj)
                            ret = max(ret, a[i][j] + a[ii][jj] - a[i][jj] - a[ii][j]);
                            //debug(a[i][j] + a[ii][jj] - a[i][jj] - a[ii][j])
                        }
                    }
                }
            }
            //disp();
            cout<<ret<<endl;
        }
        return 0;
    }

![在这里插入图片描述][20191122194630973.png]

**下面是 O ( n 3 ) O(n^\{3\}) O(n3)的解法**

**先求解每一个从i行至j行的第k列的和，从别存入dp\[k\]**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]  
**对于dp数组，我们解决最大连续子序列的和即可**

#include <iostream>
    #include <stdio.h>
    #include <limits.h>
    #include <string.h>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    int a[101][101];
    int N;
    int ret = INT_MIN;
    int dp[101];
    
    void disp(){ 
        for(int i=0;i<N;i++){ 
            for(int j=0;j<N;j++){ 
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
    }
    
    int main(){ 
        while(cin>>N){ 
            ret = INT_MIN;
            //memset(a,0,sizeof(a));
            for(int i=0;i<N*N;i++){ 
                scanf("%d",&a[i/N][i%N]);
            }
    
            for(int i=0;i<N;i++){ 
                memset(dp,0,sizeof(dp));
                for(int j=i;j<N;j++){ 
                    for( int k=0;k<N;k++ ){ 
                        dp[k] += a[ j ][k];
                    }
                    int temp = 0;
                    for( int k=0;k<N;k++ ){ 
                        temp += dp[k];
                        ret = max(ret,temp);
                        if( temp < 0 ){ 
                            temp = 0;
                        }
    
                    }
                }
            }
            cout<<ret<<endl;
        }
    }

![在这里插入图片描述][20191123201649615.png]

[20191122194630973.png]: https://img-blog.csdnimg.cn/20191122194630973.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191123203102683.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3,size_16,color_FFFFFF,t_70
[20191123201649615.png]: https://img-blog.csdnimg.cn/20191123201649615.png