Sichuan Province 2012 F Fold The Paper

---

题目描述：

F. Fold The Paper

Time Limit: 2000ms

Memory Limit: 65535KB
64-bit integer IO format: %lld Java class name: Main

Submit Status PID: 24254

You have a rectangular piece of paper that is divided into 1 × 1 cells, each of which has an integer value.

You want to perform a sequence of folds on the paper, where you may fold anywhere along an axis that is in between two rows or columns of the paper. After performing all the folds you want, the overlapping cells will be considered as a single cell, whose value is the sum of the individual cells.

You want the biggest number in the resulting piece of paper to be as large as possible, what is the biggest number you can get ?

Input

First line of the input is a single integer T(1 <= T <= 10), indicating there are T test cases. For each test case, the first line contains two integers, N and M (1 <= N <= 20, 1 <= M <= 500), indicating the length and width of the paper. Then N lines followed, each line contains M integers xi(|xi| <= 10^4), indicating the numbers in the original piece of paper.

Output

For each case,output “Case #t: ret” in a single line, where t indicating the case number between 1 and T, and ret is the biggest number you can get in the resulting piece of paper.

Sample Input

2
2 2
1 -2
3 -4
2 5
1 -2 -3 4 -5
6 -7 -8 9 -10

Sample Output

Case #1: 4
Case #2: 20

题解：

直接粘思路不手打了:

有一些你不得不知道的神秘性质：

考虑一个 1×n 的纸带，一定可以折叠，使得间隔为奇数的格子叠在一起。

所以对那个 20 搜一下，另外一维打牌就行了。

重点：

(1)性质的探索,不局限于题目描述,而是发现每次想折i的时候,和i相差奇数的都可以.
(2)这一点可能更重要:我们只要一个最大值,20的暴力枚举没必要把整个20的情况都一块搞出来再算,而是:先盯着1来看,看最后1和哪几个列混在了一块,利用强制让1是混在一块中最小的以及向后第一次折叠的技术技巧很简单的就能够向后暴力枚举(正常人可以忽略这句话…).这样到最后看到1能够和哪些联在一起.很好的思想.
(3)最后的dp.保存一下前面的以奇数和偶数结尾的最优的值,然后递推.其实这个思路也适用于20个那个的暴力,但是维护的状态更多,不如像2那样一次只考虑一次的.

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 517;
const int inf = 1e9 + 1e5;
int f[N][2];
int b[N],s[N];
int a[23][N];
int ans,n,m;

void dp(int k)
{
    memset(s,0,sizeof s);
    for (int i = 0;i <= m;i++)
    {
        f[i][0] = f[i][1] = -inf;
    }
    for (int i = 1;i <= k;i++)
    {
        for (int j = 1;j <= m;j++)
            s[j] += a[b[i]][j];
    }
    for (int i = 1;i <= m;i++)
    {
        int st = i & 1;
        f[i][st] = f[i-1][st];
        f[i][st ^ 1] = f[i-1][st ^ 1];
        //
        f[i][st] = max(f[i][st], s[i]);
        f[i][st] = max(f[i][st], f[i-1][st^1] + s[i]);

    }
    //if (k == 2) printf("%d\n",f[3][1]);
    ans = max(ans, f[m][0]);
    ans = max(ans, f[m][1]);
}

void dfs(int now,int k)
{
    if (k)
    {
        dp(k);
    }
    for (int i = now; i <= n;i += 2)
    {
        b[k+1] = i;
        dfs(i+1,k+1);
    }
}

void solve()
{
    ans = -inf;
    scanf("%d %d",&n,&m);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= m;j++)
        {
            scanf("%d",&a[i][j]);
            ans = max(ans,a[i][j]);
        }
    dfs(1,0);
    dfs(2,0);
    static int ca = 0;
    printf("Case #%d: ",++ca);
    printf("%d\n",ans);
}

int main()
{
 //   freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while (t--)
        solve();
}