CS Academy Round#5 E.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
", 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+ 行，其它题目也是的，很奇怪的长，我就不是很懂。。