题解：P13469 [GCJ 2008 #2] PermRLE

· · 题解

考虑 dp。

发现我们只关心相邻两个的关系，而且 k 比较小，所以可以考虑状压。

如果对于 i,j，我们让两者在 p 中相邻，且 i 在 j 前面，那么对于每个区间，会产生 [s_{pk+i}\ne s_{pk+j}] 的贡献，总共记作 w_{i,j}。

这个东西可以预处理出来。

然后还要考虑跨段的贡献，我们需要知道 p_0 和 p_{k-1}，这个东西枚举一下也可以求出，记作 g_{s,t}。

考虑状压 DP 的定义：f_{S,st,lst} 表示当前选择的点集是 S，起点是 st，最后一个点是 lst。

答案是：

1+ \min_{s,t<k} (f_{2^k-1,s,t}+g_{s,t})

那么转移的话，只需要枚举下一个 nex，以及当前的起点和最终点，用 w 来转移就好。

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,k;
int cnt;

string s;
int f[650005][16][16];

int g[25][25];
int w[25][25];


inline void solve(){
    cin>>k>>s;
    n=s.size();
    cnt=n/k;
    memset(g,0,sizeof(g));
    memset(w,0,sizeof(w));
    for (int S=0;S<k;S++){
        for (int T=0;T<k;T++){
            if (S==T){
                continue;
            }
            for (int p=0;p<cnt-1;p++){
                g[S][T]+=(s[p*k+S]!=s[(p+1)*k+T]);
                w[S][T]+=(s[p*k+S]!=s[p*k+T]);
            }
            w[S][T]+=(s[(cnt-1)*k+S]!=s[(cnt-1)*k+T]);
        }
    }
    for (int S=0;S<(1<<k);S++){
        for (int i=0;i<k;i++){
            for (int j=0;j<k;j++){
                f[S][i][j]=1e18;
            }
        }
    }
    for (int i=0;i<k;i++){
        f[1<<i][i][i]=0;
    }

    for (int S=0;S<(1<<k);S++){
        for (int st=0;st<k;st++){
            for (int lst=0;lst<k;lst++){
                if (S>>lst&1){
                    for (int nex=0;nex<k;nex++){
                        if (S>>nex&1){
                            continue;
                        }
                        f[S|(1<<nex)][st][nex]=min(f[S|(1<<nex)][st][nex],f[S][st][lst]+w[lst][nex]);
                    }
                }
            }
        }
    }
    int ans=1e18;
    for (int S=0;S<k;S++){
        for (int T=0;T<k;T++){
            ans=min(ans,f[(1<<k)-1][S][T]+g[S][T]+1);
        } 
    }
    cout<<ans<<"\n";
    return;
}

int T;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    for (int i=1;i<=T;i++){
        cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}