ZOJ2688 Requirements

　　原题传送：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2688

　　这题在武森的论文《浅谈信息学竞赛中的“0”和“1”》中有很精彩的讲解。

　　这道题暴力枚举肯定TLE，转而想到消去绝对值符号，式子前面加上“+”和“-”两个符号，有5维，则一共有2⁵种情况，而总的最大值是这2⁵种情况的最大值减最小值。对于每种情况，都可以O(n)求出最大值和最小值。总复杂度为O(n*2^k )，可以承受了。

#include <stdio.h>
#include <string.h>
#define N 100005

double a[N][32], data[5];

void dfs(int i, double v, int d, int k)
{
    if(d == 5)
    {
        a[i][k] = v;
        return ;
    }
    dfs(i, v + data[d], d + 1, k * 2 + 1);
    dfs(i, v - data[d], d + 1, k * 2);
}

int main()
{
    freopen("data.in", "r", stdin);
    int n, i, j;
    double max, min, ans;
    while(scanf("%d", &n), n)
    {
        for(i = 0; i < n; i ++)
        {
            for(j = 0; j < 5; j ++)
            {
                scanf("%lf", &data[j]);
            }
            dfs(i, 0.0, 0, 0);
        }
        ans = 0.0;
        for(j = 0; j < 32; j ++)
        {
            max = a[0][j], min = a[0][j];
            for(i = 1; i < n; i ++)
            {
                if(a[i][j] > max)
                    max = a[i][j];
                if(a[i][j] < min)
                    min = a[i][j];
            }
            if(max - min > ans)
                ans = max - min;
        }
        printf("%.2f\n", ans);
    }
    return 0;
}