jzoj 1307. Jail

分类讨论16种情况？？？
码量超长，想了会儿数据结构后就弃疗打暴力了。
正解时间复杂度为O(2^d * n * d)
我们枚举坐标的每个数的正负性。
然后在对于每种情况暴力弄出n个点的贡献。
由于两两之差便为曼哈顿距离。
所以我们对于每种情况求出个最大值和最小值，
两个相减再与Ans比较并更新即可。

上标：

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1000010
#define ll long long
using namespace std;
int n,D,a[N][6],c[7],s,ans=0;
bool bz;

inline int read()
{
	int x=0,f=0; char c=getchar();
	if (c==EOF) {bz=1; return 0;}
	while (c<'0' || c>'9') f=(c=='-') ? 1:f,c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f ? -x : x;
}

void dfs(int x)
{
	if (x>D)
	{
		int mi=1e9,ma=-1e9;
		for (int i=1;i<=n;i++)
		{
			s=0;
			for (int j=1;j<=D;j++)
				s+=c[j] ? -a[i][j] : a[i][j];
			if (s>ma) ma=s;
			else if (s<mi) mi=s;
		}
		if (ma-mi>ans) ans=ma-mi;
		return;
	}
	c[x]=1,dfs(x+1);
	c[x]=0,dfs(x+1);
}

int main()
{
	freopen("Jail.in","r",stdin);
	freopen("Jail.out","w",stdout);
	n=read(),D=read();
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=D;j++)
			a[i][j]=read();
		if (bz) n=i;
	}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

能看到这儿的都很有耐心啊~
那我就告诉你一点东西吧：

这题枚举D-1个符号即可！！！

至于正确性为什么能保证嘛。
我们假设D=5，

如果+ - + - -是最优解的话，

那么- + - + +也一定是最优解！！！

所以我们可以把其中一个符号固定，这样就可以将时间复杂度 div 2了！！！

上标：（快了约400ms）

#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1000010
#define ll long long
using namespace std;
int n,D,a[N][6],c[7],s,ans=0;
bool bz;

inline int read()
{
	int x=0,f=0; char c=getchar();
	if (c==EOF) {bz=1; return 0;}
	while (c<'0' || c>'9') f=(c=='-') ? 1:f,c=getchar();
	while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f ? -x : x;
}

void dfs(int x)
{
	if (x==D)
	{
		int mi=1e9,ma=-1e9;
		for (int i=1;i<=n;i++)
		{
			s=a[i][D];
			for (int j=1;j<=D-1;j++)
				s+=c[j] ? -a[i][j] : a[i][j];
			if (s>ma) ma=s;
			else if (s<mi) mi=s;
		}
		if (ma-mi>ans) ans=ma-mi;
		return;
	}
	c[x]=1,dfs(x+1);
	c[x]=0,dfs(x+1);
}

int main()
{
	freopen("Jail.in","r",stdin);
	freopen("Jail.out","w",stdout);
	n=read(),D=read();
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=D;j++)
			a[i][j]=read();
		if (bz) n=i;
	}
	dfs(1);
	printf("%d\n",ans);
	return 0;
}