CF1238E. Keyboard Purchase

非常奇妙的一道状压\(dp\)

想到状压后特别自闭的想了很久.......

首先是两个点之间的位移次数可以\(O(n)\)预处理出来，于是问题主要在于分配位置上

然后就有一个非常骚的搞法了

我们可以将每个点选/不选状压一下，但是这样肯定是不能维护选取的位置的

可以强制让被选入集合的元素的位置偏小，当然这样是对的，但是这样还需要额外维护每个点的位置复杂度仍然\(O(m!)\)

这样做之后可以将位置看作选入集合的时间，这样一样是对的，于是位置之差就可以转化为时间之差

考虑将两个点之间被选入的时间之差拆开，比如选\(a\)的时间是\(t_a\)，选\(b\)的时间为\(t_b\)，那么可以将\(|t_b-t_a|\)拆开变成\(1+1...+1\)

你会惊人的发现这个东西是可以累加的，于是每次加点实际上是将集合内所有元素与集合外的所有元素的遍历时间之差都\(+1\)，然后这样\(dp\)即可

当然要预处理出来每个状态\(\rm (\)集合\(\rm S)\)与其外的元素的位移次数总和即可，这个东西的复杂度是\(O(m^2*2^m)\)，不过跑不满

转移的话就枚举选谁即可，复杂度\(O(m*2^m)\)

复杂度\(O(m^2*2^m+n)\)

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 1e5 + 5 ; 
const int M = 21 ; 
int n, m, f[1 << M], dp[1 << M], cnt[M][M] ;
char s[N] ;
int G( char x ) {
    return x - 'a' ;
}
signed main()
{
    n = gi(), m = gi() ;  
    scanf("%s", s + 1 ) ;
    rep( i, 1, n - 1 ) ++ cnt[G(s[i])][G(s[i + 1])], ++ cnt[G(s[i + 1])][G(s[i])] ;
    int maxn = ( 1 << m ) - 1, t = m - 1 ; 
    rep( i, 1, maxn ) {
        rep( j, 0, t ) {
            if( ( ( 1 << j ) & i ) ) 
            rep( k, 0, t ) {
                if( !( ( 1 << k ) & i ) )
                f[i] += cnt[j][k] ; 
            }
        }
    }
    memset( dp, 63, sizeof(dp) ), dp[0] = 0 ;
    rep( i, 1, maxn ) {
        rep( j, 0, t ) {
            if( ( 1 << j ) & i )
            dp[i] = min( dp[i ^ ( 1 << j )] + f[i], dp[i] ) ;
        }
    }
    printf("%d\n", dp[maxn] ) ;
    return 0 ;
}

CF1238E. Keyboard Purchase

原文：https://www.cnblogs.com/Soulist/p/11656181.html