p1433

状压大炮。

一眼大炮。“状压”型号的大炮的制动方式很复杂，主要是根据二进制这一位上面是

0

或

1

来决定发射炮弹的型号。顾名思义，炮弹型号

f_{i,k}

就代表二进制为

k

时走到点

i

的炮弹。所以有

f_{i,k} =\min (f_{i,k},f_{j,k-2^{i-1}}+a_{i,j})

。（

a

数组表示两点间的距离）最后找出

\max(f_{i,2^n-1})

中间的最大值就行。

代码也是很简单……个蛋！

CPP

#include <bits/stdc++.h>
double dis[20][20];
double x[20], y[20];
double f[20][100010];
int n;
double diss(int v, int w)
{
	return sqrt((x[v] - x[w]) * (x[v] - x[w]) + (y[v] - y[w]) * (y[v] - y[w]));//算距离
}
int main()
{
	double ans;
	for (int i = 0; i < 20; i ++) for (int j = 0; j < 100010; j ++) f[i][j] = 1e9;
	ans = f[0][0];
	cin >> n
	for(int i = 1; i <= n; i ++)
	{
		cin >> x[i] >> y[i];
	}
	x[0] = 0; y[0] = 0;
	for(int i = 0; i <= n; i ++)
	{
		for(j = i + 1; j <= n; j ++)
		{
			a[i][j] = diss(i, j);
			a[j][i] = a[i][j];
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		f[i][(1 << (i - 1))] = a[0][i];
	}
	for(int k=1; k < (1 << N); k ++)
	{
		for(int i = 1; i <= n; i ++)
		{
			if((k & (1 << (i - 1))) == 0)//i压根没走过不可能成为当前走到的点
				continue;
			for(int j = 1; j <= n; j ++)
			{
				if(i == j)//一样的话等于自己走到自己，wyy
					continue;
				if((k & (1 << (j - 1))) == 0)//j 没走自然不可能走到 i
					continue;
				f[i][k] = min(f[i][k], f[j][k - (1 << (i - 1))] + a[i][j]);
			}
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		ans = min(ans, f[i][(1 << N) - 1]);
	}
	printf("%.2f\n", ans);
}

文章操作

相关推荐

评论

p1433