hdu6435 Problem J. CSGO标程讲解以及改正标程的一个错误（本来第一个样例过不了2333） 以及 poj2926 五维曼哈顿距离模板

比赛的时候抄poj2926的模板，但改不来啊orz

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int dem=;        //维数

const int maxxn=;

const double inf=1e200;

struct Point{

    double x[dem];

}p[maxxn];

int n;

double minx[<<dem], maxx[<<dem];

double solve(){

    int i, j, k, t, tmp=<<dem;

    double s, ans=-inf;

    for(i=; i<tmp; i++){

        minx[i]=inf;

        maxx[i]=-inf;

    }

    for(i=; i<n; i++){

        for(j=; j<tmp; j++){

            t=j;s=;

            for(k=; k<dem; k++){

                if(t&)

                s+=p[i].x[k];

                else s-=p[i].x[k];

                t>>=;

            }

            if(maxx[j]<s)maxx[j]=s;

            if(minx[j]>s)minx[j]=s;

        }

    }

    for(i=; i<tmp; i++){

        if(maxx[i]-minx[i]>ans)

        ans=maxx[i]-minx[i];

    }

    return ans;

}

int main(){

    //freopen("1.txt", "r", stdin);

    int i, j;

    while(scanf("%d", &n)!=EOF){

        for(i=; i<n; i++){

            for(j=; j<dem; j++)

                scanf("%lf", &p[i].x[j]);

        }

        printf("%.2f\n", solve());

    }

    return ;

}

后来看了标程，感觉上面那个算法是瞎搞的，于是改成了正确的姿势：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include<ctime>

using namespace std;

#define LL double

int T, n, m, K  ;

LL A[], B[], Ans,val,x[];

int main()

{

    int i, k, S;

        K=;

        cin>>n;

        Ans = ;

        for (int i = ; i < ; i++)A[i] = B[i] = -1e200;

        for (i = ; i <= n; i++)

        {

            for (k = ; k<K; k++)

                scanf("%lf", &x[k]);

            for (S = ; S< << K; S++)

            {

                LL Sum = ;

                for (k = ; k<K; k++)

                    Sum += x[k] * ((((S >> k) & ) << ) - );

                A[S] = max(A[S], Sum);

            }

        }

        for (S = ; S< << K; S++)

            {Ans = max(Ans, A[S] + A[( << K) -  - S]);

            }

        printf("%.2lf\n", Ans);

}

/*

3

2 5 6 2 1.5

1.2 3 2 5 4

7 5 3 2 5

*/

这个程序的二进制操作比较秀，具体来说：

((((S >> k) & 1) << 1) - 1)这一句是if(S的第k位为1)f=1; else f=-1 的缩写（感觉反而更麻烦了233）

A[S] + A[(1 << K) - 1 - S]这一句的意思是把符号相反的一组最优向量加起来。因为(1 << K) - 1 - S与S的0,1 互补，对应向量里+、- 互补。

标程唯一被hack的地方是数组初始化时用了memset，应该全部赋值为-inf

下面给出标程（改了一句）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include<ctime>

using namespace std;

#define LL long long

int T, n, m, K, val, x[];

LL A[], B[], Ans;

int main()

{

    int i, k, S;

    scanf("%d", &T);

    while (T--)

    {

        scanf("%d%d%d", &n, &m, &K);

        Ans = ;

        //memset(A, 0, sizeof(A));

        //memset(B, 0, sizeof(B));

        for (int i = ; i < ; i++)A[i] = B[i] = -1e18;

        for (i = ; i <= n; i++)

        {

            scanf("%d", &val);

            for (k = ; k<K; k++)

                scanf("%d", &x[k]);

            for (S = ; S< << K; S++)

            {

                LL Sum = val;

                for (k = ; k<K; k++)

                    Sum += x[k] * ((((S >> k) & ) << ) - );

                A[S] = max(A[S], Sum);

            }

        }

        for (i = ; i <= m; i++)

        {

            scanf("%d", &val);

            for (k = ; k<K; k++)

                scanf("%d", &x[k]);

            for (S = ; S< << K; S++)

            {

                LL Sum = val;

                for (k = ; k<K; k++)

                    Sum += x[k] * ((((S >> k) & ) << ) - );

                B[S] = max(B[S], Sum);

            }

        }

        for (S = ; S< << K; S++)

            Ans = max(Ans, A[S] + B[( << K) -  - S]);

        printf("%lld\n", Ans);

    }

}

/*

1

2 2 1

0 1

0 2

0 4

0 3

2

2 2 1

0 233

0 666

0 123

0 456

2 2 1

100 0 1000 100 1000 100

100 0

*/