fzy czn 生日赛 Journey题解

本文主要是介绍fzy czn 生日赛 Journey题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给出$n\times n$的二维数组$a$，你要选定一个长度为$n$的排列$p$，求$\sum _{i=1}^n\sum _{j=1}^n|p_i-p_j|\times a_{i,j}$的最小值。

$1\le n\le 21,1\le a_{i,j}\le 2\times 10^5$

时间限制$1000ms$，空间复杂度$512MB$。

题解

$|p_i-p_j|$显然阻碍了我们求最小值，我们令$q_{p_i}=i$，那么求出一个排列$q$即可对应到一个唯一的排列$p$。

那么原式变为

$$\sum _{i=1}^n\sum _{j=1}^n|i-j|\times a_{q_i,q_j}$$

分为$i<j$和$i>j$两种情况可得

$$\sum _{i=1}^n\sum _{j=1}^{i-1}(i-j)\times a_{q_i,q_j}+\sum _{i=1}^n\sum _{j=i+1}^n(j-i)\times a_{q_i,q_j}$$

后半部分$\sum _{i=1}^n\sum _{j=i+1}^n(j-i)\times a_{q_i,q_j}=\sum _{j=1}^n\sum _{i=1}^{j-1}(i-j)\times a_{q_i,q_j}=\sum _{i=1}^n\sum _{j=1}^{i-1}(i-j)\times a_{q_j,q_i}$

那么原式为

$$\begin{array}{rl}& \sum _{i=1}^n\sum _{j=1}^{i-1}(i-j)\times (a_{q_i,q_j}+a_{q_j,q_i})\\ =& \sum _{i=1}^{n}i\sum _{j=1}^{i-1}(a_{q_i,q_j}+a_{q_j,q_i})-\sum _{j=1}^{n}j\sum _{i=1}^{j-1}(a_{q_i,q_j}+a_{q_j,q_i})\\ =& \sum _{i=1}^{n}i\times [\sum _{j=1}^{i-1}(a_{q_i,q_j}+a_{q_j,q_i})-\sum _{j=i+1}^n(a_{q_i,q_j}+a_{q_j,q_i})]\end{array}$$

也就是要求一个排列$q$，使得这个式子最小。

我们假设当前已经选出了前$i-1$个$q$值，现在要将$q_i$赋为$k$，求$q_i$对答案的贡献$tmp$。对于$1\le j<i$，则$tmp$加上$(a_{k,q_j}+a_{q_j,k})$；如果$i<j\le n$，则$tmp$减去$(a_{k,q_j}+a_{q_j,k})$。最后将$tmp$乘上$i$即可得到$q_i$对答案的贡献。

我们考虑用状压$DP$。设$S$表示当前已经加入排列$q$的数，$f_S$表示$S$对应的贡献。那么当每次加入一个$k$时，可以$O(n)$计算贡献。总共可以选择$O(n)$个$k$值，那么总时间复杂度为$O(n^2{2}^n)$。常数比较小，而且跑不满，所以这是可以过的。

code

#include<bits/stdc++.h>
using namespace std;
int n,ct[1<<21];
long long a[25][25],f[1<<21];
int lb(int i){return i&(-i);
}
long long pt(int s,int wt){int p=ct[s]+1;long long tmp=0;for(int i=1;i<=n;i++){if(i==wt) continue;if((s>>i-1)&1) tmp+=a[wt][i]+a[i][wt];else tmp-=a[wt][i]+a[i][wt];}tmp*=p;return tmp;
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%lld",&a[i][j]);}}f[0]=0;for(int s=1;s<1<<n;s++){f[s]=1e18;ct[s]=ct[s^lb(s)]+1;for(int i=1;i<=n;i++){if(!((s>>i-1)&1)) continue;f[s]=min(f[s],f[s^(1<<i-1)]+pt(s^(1<<i-1),i));}}printf("%lld",f[(1<<n)-1]);return 0;
}

这篇关于fzy czn 生日赛 Journey题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---