清北学堂 青春

青春
【问题描述】
现在有一个被1× 1的小格子分割的矩形纸片，每个小格子内包含一个整数。
现在你可以进行一系列的折叠， 每次折叠的折痕必须是分割两行或者两列小格子
的分割线。
在折叠完之后，所有重叠的小格子被看作一个单独的格子，并且这个格子的
价值为重叠的小格子的价值和。
你想要知道，在所有可能得到的新格子中，格子价值的最大值为多少。
【输入格式】
输入文件的第一行有两个整数?和?,分别表示初始的矩形纸片的长和宽。接
下来的?行，每行有?个数字表示初始的小格子内的整数。
【输出格式】
输出一行表示所能得到的格子价值的最大值。
【样例输入】
2 2
1 -2
3 -4
【样例输出】
4
【样例解释】
无。
【数据规模与约定】
对于100%的数据，格子内的数字权值的绝对值不超过10000。
数据点 ? ? 数据点 ? ?
1 3 3 6 15 100
2 10 10 7 20 100
3 10 10 8 20 500
4 15 15 9 20 500
5 20 20 10 20 500

/*dfs 枚举所有对折情况 找出最大值 未优化70分 30分爆空间*/
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,ans=1<<31,arr[20][500],t[500],mm[500];
void dfs(int p)
{
    for(int i=0;i<m;i++) //t[i]表示到当前行第i列的所有元素的和 
        t[i]+=arr[p][i];
    for(int j=m-1;~j;j--) //找出当前行前j列的和的最大值
    {
        mm[j]=t[j]; 
        ans=max(ans,mm[j]);
        for(int k=0;j+k*2+1<m;k++) //对折枚举 
        {
            mm[j]=max(mm[j],t[j]+mm[j+k*2+1]);
            ans=max(ans,mm[j]);
        } 
    }
    for(int j=0;p+j*2+1<n;j++) //对折枚举 
        dfs(p+j*2+1); 
    for(int i=0;i<m;i++) 
        t[i]-=arr[p][i]; 
}
int main(){
    freopen("taritari.in","r",stdin);
    freopen("taritari.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&arr[i][j]);
    for(int i=0;i<n;i++) 
        dfs(i);
    printf("%d
",ans);
    return 0;
}