Educational Codeforces Round 74

發表於 更新於 分類於 ， Disqus： 文章字數： 620 所需閱讀時間 ≈ 2 分鐘
E (bitDP)

原题链接

大意

前m个字母的所有排列中

对于字符串s

求min{sum{f(s[i-1],s[i])}} ，i = [1,len(s)-1]

f(char1,char2) = 在所选排列中 这两个char的下标差的绝对值

数据范围

1<=m<=20

1<=len(s)<=100000

1s

256MB

题解

显然把 字符串处理为统计信息一个m*m的表M

其中M[char1][char2]表示 字符char1和char2相邻的次数

然后看到 20/12都应该想一想 bitdp

dp[state] 表示前 bitcount(state)个数选择了state时的最优代价;

那么我们在 这个状态后面 添加一个未选取的数v

那么 [选取的数的状态][数字v]

问题来了

前面的最优状态如果没有具体位置,那么 v到已经选择的数字的 距离不同，所以权重也就不同,而即使 在最优代价中加上具体状态的记录，也不满足 子最优必定父最优

怎么把 选取的数字的顺序无关化?

考虑已经完全选好的一个排列

xyzabc

那么这个贡献 也就是 dis(x,y)*M[x][y]+dis(x,z)*M[x][z]+....+dis(b,c)*M[b][c]

如果我们画图把 这些点用线连起来

从中间切一刀，例如从xyz|abc这里切分, 会发现 a连出的线条数和 左边排列顺序无关，只和左边个数以及a相对于分割线的位置有关，

考虑 xyz|abc -> xyza|bc ,xya|zbc -> xyaz|bc

所以上面dp[state]的描述 改为 bitcount(state)个数选择了state时，且向右连线到分界线时的最优代价

注意新的分界线 增加的值和老的分界线 没有关系 所以只需要 O(m^2 * 2^m)而不是 m^3

代码

source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
int n,m;
char s[100010];
 
int cnt[30][30];
ll dp[(1<<20)+10];
 
int main(){
  cin>>n>>m;
  scanf("%s",s);
  rep(i,1,n){
    cnt[s[i-1]-'a'][s[i]-'a']++;
    cnt[s[i]-'a'][s[i-1]-'a']++;
  }
  rep(state,1,1<<m){
    int ii = state;
    dp[state] = 0x3f3f3f3f;
    while(ii){
      int bit = ii & (-ii);
      ll costbit = dp[state^bit];
      dp[state]=min(dp[state],costbit);
      ii^=bit;
    }
    // 增加切割的分界线即可
    rep(i,0,m){
      if(!(state & (1<<i)))continue;
      rep(j,0,m){
        if(state & (1<<j))continue;
        dp[state]+=cnt[i][j];
      }
    }
  }
  cout<<dp[(1<<m)-1]<<endl;
  return 0;
}