关于状态压缩的空间优化问题
查看原帖
关于状态压缩的空间优化问题
378467
Windy_YY楼主2022/10/4 19:19

请问,怎么减少程序的内存?(已经过了但是想要优化,请不要说暴力搜索之类的飞状态压缩方法)

#include <bits/stdc++.h>

using namespace std;

int f[1 << 20][20], a[22][22];

signed main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < n; j ++)
			cin >> a[i][j];
	memset (f, 0x3f, sizeof f);
	f[1][0] = 0;
	for (int i = 1; i < (1 << n); i ++)
		for (int j = 0; j < n; j ++)
			if (i & (1 << j))
				for (int k = 0; k < n; k ++)
					if (~i & (1 << k))
						f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + a[j][k]);
	int mi = 1e9;
	for (int i = 1; i < n; i ++)
		mi = min(mi, f[(1 << n) - 1][i] + a[i][0]);
	cout << mi << '\n';
	return 0;
}

2022/10/4 19:19
加载中...