点击打开poj 2926
思路: n维空间计算最远的曼哈顿距离
分析:
1 题目给定n个5维的点,要求最远的曼哈顿距离
2 求最远曼哈顿距离,对于一个n维的空间,其中两点的曼哈顿距离为:|x1-x2|+|y1-y2|+... , 两点的坐标分别为(x1,y1……)和(x2,y2,……)
3 考虑二维的情况
对于二维空间的两个点(x1,y1)和 (x2,y2),那么曼哈顿距离为|x1-x2|+|y1-y2|
那么我们去掉绝对值之后就有四种情况(x1-x2)+(y1-y2) , -(x1-x2)+(y1-y2) ,(x1-x2)-(y1-y2)
,-(x1-x2)-(y1-y2)
那么我们把相同点的放在一起变形一下得到(x1+y1)-(x2+y2) ,(-x1+y1)-(-x2+y2) ,(x1-y1)-(x2-y2) , (-x1-y1)-(-x2-y2)
那么很明显我们只要去求出4种组合方式的最大和最小值,然后求最大的(最大值-最小值)
4 对于n维的空间来说这个结论也是正确的,n维的话就有2^n种状态,我们只要去枚举n个点然后求每一种状态的最大值和最小值,然后求最大的(最大值-最小值)
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5;
const int INF = 1<<30;
const int MAXN = 100010;
struct Node{
double p[N];
};
Node node[MAXN];
int n;
double maxNum[MAXN];
double minNum[MAXN];
void init(){
for(int i = 0 ; i < (1<<N) ; i++){
maxNum[i] = -INF;
minNum[i] = INF;
}
}
double solve(){
init();
double ans = 0;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < (1<<5) ; j++){
int s = j;
double sum = 0;
for(int k = 0 ; k < 5 ; k++){
if(s&(1<<k))
sum += node[i].p[k];
else
sum -= node[i].p[k];
}
maxNum[j] = max(maxNum[j] , sum);
minNum[j] = min(minNum[j] , sum);
}
}
for(int i = 0 ; i < (1<<N) ; i++)
ans = max(ans , maxNum[i]-minNum[i]);
return ans;
}
int main(){
while(scanf("%d" , &n) != EOF){
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < N ; j++)
scanf("%lf" , &node[i].p[j]);
printf("%.2lf\n" , solve());
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告
poj 3083解题报告poj 3083解题报告poj 3083解题报告poj 3083解题报告