FZU 1018 枚举dp

题意 给出一个数字组成的立方体 在其中选取一个体 使这个体中的数字之和最小 不可以不选

fzu的题目分类动态规划里面不是按难度排得 是按照题号..记得以前做题碰到过算 矩阵里面求子矩阵的最大和的 不会

然后这次看着这个三维的..内心是崩溃的

幸好看了一眼范围 亮点是1<=n<=20 那直接处理一下暴力就可以了…

我们可以用一个dp[i][k][j]来记录 从1.1.1到i.k.j 之间的体的和 然后我们可以进行枚举每个体 处理的时间复杂度可以忽略 实际枚举的复杂度是n^6

但是做题的时候没有想到如何记录体的和 最后枚举起来也比较麻烦 于是采用了dp[i][k][j]中 i仅仅起到记录维度的作用 后两个度记录的才是1.1-k.j的矩阵的和 即下面的代码 操作更为简单

做好枚举矩阵之后 枚举维度相加就可以 这样其实和枚举体的时间复杂度一样

如何做到枚举体呢？

在输入的预处理上做一下变动就好..即..

cin>>a[i][k][j];
dp[i][k][j]=dp[i][k-1][j]+dp[i][k][j-1]-dp[i][k-1][j-1]+a[i][k][j];
dp[i][k][j]+=dp[i-1][k][j];

(做题的时候真是傻)..

下面是仅仅使用dp记录单维度矩阵的代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<math.h>
#include<iostream>
using namespace std;
int n;
int a[25][25][25];
int dp[25][25][25]; /// wd x y
int ans;
int main(){
    while(cin>>n)
    {
        if(n==0)
            break;
        ans=-999999999;
        memset(dp,0,sizeof(dp));
        /// 维度并不在dp中显示
        /// k与j 表示的 x y 即从1.1-x.y 这个矩形的面积
        for(int i=1;i<=n;i++) /// wd
        {
            for(int k=1;k<=n;k++) /// x
            {
                for(int j=1;j<=n;j++) /// y
                {
                    cin>>a[i][k][j];
                    dp[i][k][j]=dp[i][k-1][j]+dp[i][k][j-1]-dp[i][k-1][j-1]+a[i][k][j];
                }
            }
        }
        /// o t s f v i
        int res;
        for(int o=1;o<=n;o++)
        {
            for(int t=o;t<=n;t++)
            {
                for(int s=1;s<=n;s++)
                {
                    for(int f=s;f<=n;f++)
                    {
                        res=0;
                        /// 枚举每个二维矩阵
                        /// dp[t][f]+dp[t][f-1]+dp[t-1][f]-3*dp[o-1][s-1]
                        for(int v=1;v<=n;v++)
                        {
                            for(int i=v;i<=n;i++) /// 枚举维度
                            {
                                res=0;
                                for(int q=v;q<=i;q++)
                                {
                                    res+=(dp[q][t][f]-dp[q][t][s-1]-dp[q][o-1][f]+dp[q][o-1][s-1]);
                                }
                                if(res>ans)
                                    {
                                        ans=res;
                                    }
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
}