题目链接

CsAcademy Beta Round #5 Binary Matching

题目大意

有俩 \(01\) 串 \(a\) 和 \(b\)，你需要把 \(a\) 中的一些相邻元素互换，使得 \(b\) 在 \(a\) 匹配的次数尽量多，求最大的匹配次数以及达到这个状态所需的最少步数。

串的长度 \(\in[1, 500]\)

思路

如果你的思路是这样的：“最大匹配次数好像很好求，我先把这个求出来，然后构造个串 \(c\) 给 \(a\) 求最少步数应该就可以了。” 那么真巧，你跟我开始一样误入歧途了，其实 \(c\) 这个串具有很大的灵活性，算起来相当麻烦。

讲正确的做法，要 \(dp\) 的话我们从前往后扫 \(a\)，这是一个类似于 \(KMP\) 和 \(b\) 匹配的过程，那么应该可以想到这样一个状态：\(dp[i][j][k]=(max\_matchings,min\_operations)\) ，\(i\) 和 \(j\) 表示当前有的 \(0\) 和 \(1\) 的个数，\(k\) 表示匹配到了 \(b\) 的第 \(k\) 位，转移时枚举下一位是 \(0\) 还是 \(1\)，找到下一个状态的 \(k\) 直接做 \(KMP\)，步数看当前的 \(1\) 与 \(a\) 中 对应的 \(1\) 的距离即可（如果是 \(0\) 就不管）。

时间复杂度： \(O(n^3)\)

不过呢，这题空间时间都卡，内存只有 \(128 MB\)，需要滚动 \(dp\)。时限 \(1000ms\)，可以预处理 \(KMP\) 中跳 \(nxt\) 的结果，对于达不到的状态直接 continue ，这样就可以最优解 rank 5 了。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define mem(a,b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 505
#define PII pair<int, int>
#define fr first
#define sc second
#define Inf 0x3f3f3f3f
using namespace std;
string a, b;
PII dp[2][N][N];
int n, m, nxt[N], loc[N], match[N][2];
void kmp(){
    nxt[0] = 0;
    int j = 0;
    rep(i,1,m-1){
        while(j > 0 && b[i] != b[j]) j = nxt[j-1];
        if(b[j] == b[i]) j++;
        nxt[i] = j;
    }
}
void Trans(PII &a, PII b){
    if(a.fr < b.fr) a = b;
    else if(a.fr == b.fr) a.sc = min(a.sc, b.sc);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>a>>b;
    n = a.size(), m = b.size();

    kmp();
    rep(i,0,m) rep(c,'0','1'){
        int tmp = i;
        while(tmp > 0 && b[tmp] != char(c)) tmp = nxt[tmp-1];
        if(b[tmp] == char(c)) tmp++;
        match[i][c-'0'] = tmp;
    }
    int cnt = 0;
    rep(i,0,n-1) if(a[i] == '1')
        loc[++cnt] = i;

    mem(dp, 0x80), dp[0][0][0] = {0, 0};
    rep(i,0,n-cnt) rep(j,0,cnt) rep(k,0,m){
        if(dp[i%2][j][k].fr < 0) continue;
        //printf("dp[%d][%d][%d] : %d %d\n", i, j, k, dp[i%2][j][k].fr, dp[i%2][j][k].sc);
        rep(c,'0','1'){
            int tmp = match[k][c-'0'];
            PII cur = dp[i%2][j][k];
            cur.fr += (tmp == m);
            if(c == '0') Trans(dp[(i+1)%2][j][tmp], cur);
            if(c == '1') cur.sc += abs(loc[j+1]-(i+j)), Trans(dp[i%2][j+1][tmp], cur);
        }
        if(i%2 != (n-cnt)%2 || j != cnt) dp[i%2][j][k] = {-Inf, -Inf};
    }

    PII ans = {0, 0};
    rep(k,0,m) Trans(ans, dp[(n-cnt)%2][cnt][k]);
    cout<<ans.fr<<" "<<ans.sc<<endl;
    return 0;
}

吐槽一下这个网站上人的码风，一个 63 行代码就可以解决的题目，为什么大家都写了 100+ 行，其它题目也是的，很奇怪的长，我就不是很懂。。