交易平台网站开发教程百度云,设计网站名称,西安企业招聘,中国石化工程建设有限公司首页problem
luogu-P6622
一条道路上从左至右排列着 mmm 个信号站#xff0c;初始时从左至右依次编号为 1,2,…,m1,2,\dots,m1,2,…,m#xff0c;相邻信号站之间相隔 111 单位长度。
每个信号站只能往它右侧的任意信号站传输信号#xff08;称为普通传递#xff09;#xf…problem
luogu-P6622
一条道路上从左至右排列着 mmm 个信号站初始时从左至右依次编号为 1,2,…,m1,2,\dots,m1,2,…,m相邻信号站之间相隔 111 单位长度。
每个信号站只能往它右侧的任意信号站传输信号称为普通传递每单位长度距离需要消耗 111 单位时间。
道路的最左侧有一个控制塔它在最左侧信号站的左侧与其相隔 111 单位长度。
控制塔能与任意信号站进行双向信号传递称为特殊传递但每单位长度距离需要消耗 kkk 个单位时间。
对于给定的长度为 nnn 的信号传递序列 SSS传递规则如下
共 n−1n-1n−1 次信号传递第 iii 次信号传递将把信号从 SiS_iSi 号信号站传递给 Si1S_{i1}Si1 号。若 Si1S_{i1}Si1 号信号站在 SiS_iSi 号右侧则将使用普通传递方式从 SiS_iSi 号直接传递给 Si1S_{i1}Si1 号。若 Si1S_{i1}Si1号信号站在 SiS_iSi 号左侧则将使用特殊传递方式信号将从 SiS_iSi 号传递给控制塔再由控制塔传递给 Si1S_{i1}Si1 号。若 SiSi1S_iS_{i1}SiSi1则信号无须传递。
阿基作为大工程师他能够任意多次交换任意两个信号站的位置即他能够重排信号站的顺序这样会使得 SSS 消耗的传递时间改变。
现在阿基想知道在他重排信号站顺序后SSS 所消耗的传递时间最小能是多少。
solution
假设坐标在 x,yx,yx,y 的两个信号塔之间有一次 x→yx\rightarrow yx→y 的传递可以形式化地表示 {y−xx≤ykxkyxy\begin{cases} y-xx\le y\\ kxkyxy \end{cases} {y−xkxkyx≤yxy 这是同构的也就是说对于每个传递的贡献可以拆成两个信号塔的各自贡献。
假设坐标在 yyy 的信号塔如果有坐标 x→yx\rightarrow yx→y 的传递。
则对于 yyy 所代表的信号塔而言 x≤yx\le yx≤y产生 111。xyxyxy产生 kkk。 反之同理对于 xxx 所代表的信号塔而言 x≤yx\le yx≤y产生 −1-1−1。xyxyxy产生 kkk。
则最终代价等于每个点的贡献乘以其坐标再求和。
具体的数学形式推导
设 cnt(i,j):cnt(i,j):cnt(i,j): 有多少次信号塔 i→ji\rightarrow ji→j 的传递即 cnt(i,j)∑k1n[Ski][Sk1j]cnt(i,j)\sum_{k1}^n[S_ki][S_{k1}j]cnt(i,j)∑k1n[Ski][Sk1j]。
设下标 ppp 处是 idpid_pidp 号信号站推导一下每个下标对答案的贡献。 ans∑i1m∑ji1mcnt(idi,idj)∗(j−i)∑i1m∑j1i−1cnt(idi,idj)∗(ij)∗kans\sum_{i1}^m\sum_{ji1}^mcnt(id_i,id_j)*(j-i)\sum_{i1}^m\sum_{j1}^{i-1}cnt(id_i,id_j)*(ij)*k ansi1∑mji1∑mcnt(idi,idj)∗(j−i)i1∑mj1∑i−1cnt(idi,idj)∗(ij)∗k∑i1mi(∑ji1m(k∗cnt(idj,idi)−cnt(idi,idj))∑j1i−1(k∗cnt(idi,idj)cnt(idj,idi)))\sum_{i1}^mi\bigg(\sum_{ji1}^m\Big(k*cnt(id_j,id_i)-cnt(id_i,id_j)\Big)\sum_{j1}^{i-1}\Big(k*cnt(id_i,id_j)cnt(id_j,id_i)\Big)\bigg) i1∑mi(ji1∑m(k∗cnt(idj,idi)−cnt(idi,idj))j1∑i−1(k∗cnt(idi,idj)cnt(idj,idi)))
设 f(s):f(s):f(s): 考虑到 ∣s∣|s|∣s∣ 位∣s∣:s|s|:s∣s∣:s 二进制下 111 的个数前 ∣s∣|s|∣s∣ 位的信号站编号集合为 sss 时的最小代价。
那么 ∑ji1m(k∗cnt(idj,idi)−cnt(idi,idj))∑j1i−1(k∗cnt(idi,idj)cnt(idj,idi))\sum_{ji1}^m\Big(k*cnt(id_j,id_i)-cnt(id_i,id_j)\Big)\sum_{j1}^{i-1}\Big(k*cnt(id_i,id_j)cnt(id_j,id_i)\Big)∑ji1m(k∗cnt(idj,idi)−cnt(idi,idj))∑j1i−1(k∗cnt(idi,idj)cnt(idj,idi)) 形式中的 jjj 其实就是以 ∣s∣|s|∣s∣ 为划分点分成在 sss 集合内的编号信号塔和不在的信号塔。
于是我们可以预处理这部分的贡献只需要知道 iii 和集合 sss 即可。
规范化的令 g(i,s)∑j∉s∧j≠ik∗cnt(idj,idi)−cnt(idi,idj)∑j∈sk∗cnt(idi,idj)cnt(idj,idi)g(i,s)\sum_{j\not\in s\wedge j\ne i}k*cnt(id_j,id_i)-cnt(id_i,id_j)\sum_{j\in s}k*cnt(id_i,id_j)cnt(id_j,id_i)g(i,s)∑j∈s∧jik∗cnt(idj,idi)−cnt(idi,idj)∑j∈sk∗cnt(idi,idj)cnt(idj,idi)。
先预处理 g(i,0)g(i,0)g(i,0)然后每次枚举 sss 二进制下的一个 111随便拎个 lowbitlowbitlowbit 位即可 O(1)O(1)O(1) 转移。
一个数从 ∉s\not\in s∈s 到变成 ∈s\in s∈s先减去原来的代价再加上 ∈s\in s∈s 里面时计算的代价。
时间复杂度 O(2mm)O(2^mm)O(2mm)。
那么 fff 数组的转移就比较简洁了枚举 sss 二进制下的 111 位置取较小值。 f(s)mini∈s{f(s−{i})∣s∣g(i,s−{i})}f(s)\min_{i\in s}\Big\{f(s-\{i\})|s|g(i,s-\{i\})\Big\} f(s)i∈smin{f(s−{i})∣s∣g(i,s−{i})} 到此时空复杂度均为 O(m2m)O(m2^m)O(m2m)。
发现空间起飞了。其实观察数据分布就会发现mmm 的变化只有 111对空间的限制明显狠于时间。
也就是说难得的需要来考虑卡一下空间了。
有各种大力优化空间的妙做法但是从应试角度以及出题角度私以为这种做法以及可以应付了
转移方程中 g(i,s)g(i,s)g(i,s) 若 i∈si\in si∈s 则是不合法的显然不会被用到。
换言之对于每个 iii最多只有 2222^{22}222 种状态。
如果只存合法状态内存就会 /2/2/2在时间上而言是常数的东西这里就是个大优化了。
考虑怎么减半
只用让每个 sss 的前 i−1i-1i−1 位不动(s(1i)-1)其余位置整体右移一位相当于 /2/2/2(s^(s(1i)-1))1最后把两者加起来即可。
code
#include bits/stdc.h
using namespace std;
#define maxn 23
int n, m, k;
int f[1 maxn], g[maxn][1 maxn - 1], cnt[maxn][maxn];
int lowbit( int x ) { return x -x; }
int main() {scanf( %d %d %d, n, m, k );for( int i 1, x, lst -1;i n;i ) {scanf( %d, x ); x --;if( ~ lst ) cnt[lst][x];lst x;}for( int i 0;i m;i ) {for( int j 0;j m;j )if( i ^ j ) g[i][0] k * cnt[j][i] - cnt[i][j];for( int s 1;s (1 m);s )if( ! (s i 1) ) {int t s ^ lowbit( s );int j __builtin_ffs( s ) - 1;g[i][(s (1i)-1) ((s ^ (s (1i)-1)) 1)] g[i][(t (1i)-1) ((t ^ (t (1i)-1)) 1)] (k * cnt[i][j] cnt[j][i]) - (k * cnt[j][i] - cnt[i][j]);}}memset( f, 0x3f, sizeof( f ) ); f[0] 0;for( int s 1;s (1 m);s ) {int x __builtin_popcount( s );for( int i 0;i m;i )if( s i 1 ) {int t s ^ (1 i);f[s] min( f[s], f[t] x * g[i][(t (1i)-1) ((t ^ (t (1i)-1)) 1)] );}}printf( %d\n, f[(1 m) - 1] );return 0;
}
