设状态为 fs,i 表示删掉了 s 这个集合内的数，最后一个删掉的为 i。
转移是 j∈/s，计算吃掉 i 后到要去吃 j 要多少次操作，也就是他们中间有多少张牌。可以 O(nm3) 预处理，在转移时 O(m) 计算贡献，总复杂度 O((n+2m)m3)。
假设吃掉牌的顺序为 p1,p2,…,pm，注意到操作 1 的次数为 pi−1 在 pi 下的 m−i 的和。
感性理解一下，实际上需要得到一张牌被送入牌堆底的总次数，如果 pi−1 在 pi 下，pi 到 pi−1 的牌会在删 pi−1 这一轮被送到牌堆底，剩下的会在删 pi 这一轮都被送到牌堆底，被操作的数量是 m−i。对于 pi−1 在 pi 上的情况，pi−1 和 pi 之间的牌会和某次删牌构成之前的情况从而被统计贡献。
O(m2) 预处理，总复杂度 O((n+2m)m2)。
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
| const int N = 22;
int f[1<<N][N];
int a[N],c[N][N];
int n,m;
int main(){
n = in,m = in;
for(int k=0;k<n;k++){
for(int j=0;j<m;j++){
a[j] = (int)in-1;
for(int i=0;i<j;i++)
c[a[i]][a[j]]++;
}
}
memset(f,0x3f,sizeof(f));
for(int k=0;k<m;k++)
f[1<<k][k] = 0;
for(int k=1;k<(1<<m);k++){
int w = __builtin_popcount(k);
for(int j=0;j<m;j++)
if((k>>j)&1)
for(int i=0;i<m;i++)
if(!((k>>i)&1))
f[k^(1<<i)][i] = min(f[k^(1<<i)][i],f[k][j]+(m-w)*c[i][j]);
}
int ans = 1e9;
for(int k=0;k<m;k++)
ans = min(ans,f[(1<<m)-1][k]);
cout << ans;
return 0;
}
|