[loj3302]信号传递

由于n较大，可以将n个数中的关系对数量记录在$m*m$的矩阵中，记作$a[i][j]$

考虑朴素的状压dp枚举排列，即$f[i]$表示以i中的数的一种排列为整个序列的前缀的最小代价，然后转移枚举下一个数j以及与其相关的数k，那么有转移$f[i|j]=min(f[i]+(|i|+1)(sum_{kin i}limits (tcdot a[j][k]+a[k][j])+sum_{k otin i}limits (tcdot a[k][j]-a[j][k])))$，时间复杂度为$o(m^{2}cdot 2^{m})$

对时间优化，对于一个i，需要快速求出下一个数为j时$|i|+1$的系数，设为$g[i][j]$，考虑从$i-lowbit(i)$转移，那么有转移$g[i][j]=g[i-k][j]+tcdot a[j][k]+a[k][j]-(tcdot a[k][j]-a[j][k])$，其中$k=lowbit(i)$，时间复杂度降为$o(mcdot 2^{m})$，但空间复杂度变为$o(mcdot 2^{m})$

对空间优化，有一个十分巧妙的做法：考虑g中修改1位的复杂度为$o(m)$，同时由于对0不断高精度+1加到$2^m$复杂度均摊$o(1)$，那么从小到大枚举i并对g暴力修改即可，时间复杂度不变，空间复杂度降为$o(2^{m}+m)$

 

#include<bits/stdc++.h>
using namespace std;
int n,m,t,x,y,a[105][105],f[10000005],g[105];
int main(){
    scanf("%d%d%d",&m,&n,&t);
    for(int i=1;i<=m;i++){
        scanf("%d",&y);
        y--;
        if (i>1)a[x][y]++;
        x=y;
    }
    for(int i=0;i<n;i++)a[i][i]=0;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=0;i<(1<<n);i++){
        int s=1,l=i-(i&(i-1));
        for(int j=0;j<n;j++)s+=((i&(1<<j))>0);
        for(int j=0;(1<<j)<=l;j++)
            for(int k=0;k<n;k++)
                g[k]=g[k]+(t*a[k][j]+a[j][k]+a[k][j]-t*a[j][k])*(1-2*((1<<j)<l));
        if (!l)l=(1<<n);
        for(int j=0;(1<<j)<=l;j++){
            g[j]=0;
            if ((1<<j)<l)
                for(int k=0;k<n;k++)
                    if ((i&(1<<k))==0)g[j]+=t*a[k][j]-a[j][k];
                    else g[j]+=t*a[j][k]+a[k][j];
        }
        for(int j=0;j<n;j++)
            if ((i&(1<<j))==0)f[i|(1<<j)]=min(f[i|(1<<j)],f[i]+s*g[j]);
    }
    printf("%d",f[(1<<n)-1]);
}