题解 | #牛牛的计算机内存#

题目大意：

每次选择一条指令直到被选完为止，每次选择一条指令的花费为这条指令里面有多少个之前没有被选的内存k，花费加$k^{2}k^2$,求最后的花费最小。

1 .选择情况有种，使用状态压缩。

2.d$p[i]\mathrm{：}ip[i]：i$为此时1-n条指令里面的选择情况，$dp[i]dp[i]$为最小花费。$vis[i]vis[i]$: i$\mathrm{为}\mathrm{此}\mathrm{时}1-n\mathrm{条}\mathrm{指}\mathrm{令}\mathrm{里}\mathrm{面}\mathrm{的}\mathrm{选}\mathrm{择}\mathrm{情}\mathrm{况}\mathrm{，}为此时1-n条指令里面的选择情况，$dp[i]$为此时指令选择情况里面的每个内存的选择情况。

3.转移方程：,$f(vis[i],a[j])f(vis[i],a[j])$为此时选第j条指令时增加的花费。

using namespace std;
const int N = 21, INF = 0x3f3f3f3f;
int dp[1 << N], vis[1 << N]; //dp [i] i为状态压缩的1-n每一位的选择情况的最小花费 ，
int n, m;
int a[25];

int cal(string s)
{
	int ans=0;
    for(int i=0;i<s.size();i++)
    {
        ans=ans*2+s[i]-'0';
    }
	return ans;
}

int f(int t1, int t2)
{
	int ans = 0;
	for (int i = 0; i < 21; i++)
	{
		if (((t1>>i&1)==0)&&(t2>>i&1))
		{
			ans++;
		}
	}
	return ans * ans;
}



int main()
{
	memset(dp, 0x3f, sizeof(dp));
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		a[i] = cal(s);
	}
	int mx = (1 << n) - 1;
	dp[0] = 0;
	for (int i = 0; i <= (1 << n) - 1; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (i>>j&1) continue;
			int tep = dp[i] + f(vis[i], a[j+1]);
			if (tep < dp[i | (1 << j)])
			{
				dp[i | (1 << j)] = tep;
				vis[i | (1 << j)] = vis[i] | a[j+1];
			}
		}
	}
	cout << dp[mx] << endl;
}