ZOJ 3539. Compress the String

Brief description:

… 定義某個字串的壓縮演算法,用一組字串壓縮一個字元串。
方法是前面的字元串可以引用其後面出現的字元串然後在其原地擴展。。。

要求 s[1] 展開之後是原字元串,給定字元串數組的長度 N, 每個分解串的限制長度 Li。。
問是否存在無損壓縮的方案。。
( .. . N <= 4, Li <= 4 .. .Sigma = 26 .. .)

Analysis:

。比賽的時候是沒有時間夠我邊想邊寫了。。賽後搞掉吧。。
。。這個搜索題還是很有想法的(雖然本體也只是個弱化版而已。。。么。。)。
但是還是很不好寫吧。。花了 2 個小時。。中間還 NC 把最後的目標串理解成 s[1] + s[2] + … + s[4] …
(因為這樣可以用.. 自動機優化。。。)

好吧。。。對於這題的話。。相信每個人都會有不同的寫法。。寫下我的吧。。

首先。最後的待壓縮串的信息只直接和 s[1] 關聯。。但是要確定 s[1] 串的話,又必須要有後面所有串的信息。。
這樣搜索的順序的話。。必須要從後面的串開始。。但是這樣又沒有直接的壓縮串的信息可供剪枝所以很是麻煩。。

(大概我認為的這題主要的難點就在上面這裡了。。而顯然上面那句話又是不對的。。題目里只有 4 個長度的限制信息和待壓縮串的信息。。
。。那麼可以當做 s[3], s[2], s[1] 的串一定會非常稀少。。但是這一步要怎麼做呢。。?。。可以對待壓縮串分析出一個信息含量的數字出來么?。。。
。。執行何種字元串演算法?最大重複子串擴展?。。嗯嗯。。有待我進一步挖掘。。。)

我的想法就是要在盡量少用剪枝的情況。。而通過對搜索結構的優化來達到目的。。。
。權衡之後。。我決定採取外層第一層 dfs() 僅確定長度和擴展位置。。對每一組合法的模糊解。。。
。第二層再 check() 判定其是否有真的合法的方法。。

然後剪枝只使用兩條。。

  1. 可行性剪枝。。(對外層 dfs()。。記錄當前最長的分解串長度。。如果不加這層剪枝。。。在搜索的第一階段就 TLE 了。。)
  2. 改變搜索順序。。(以對有解的情況下儘可能發現正解。。這剪枝一向很能打不是么?。 。。)。。
  3. (居然這就過了。。可見數據還是弱。。)

    3770 ms。。代碼長度 100 行的樣子。。。
    (。。完整代碼請移步這裡。。)

.. .
const int N = 4, M = 500, L = 4;
 
char S[M]; int len;
int s[N][L]; int _l[N], l[N], ll[N];
int n;
 
const int Normal = -1;
bool C[N]; int st[N];
bool check(){
 
    RST(C); C[n-1] = true, st[n-1] = 0;
 
    DWN(k, n, 1) if (C[k]){
        int p = st[k];
        REP(i, l[k]){
 
#define j s[k][i]
 
            if (j == Normal){
                ++p;
            }
            else {
                if (C[j]){
                    REP(ii, ll[j]){
                        if (S[p+ii] != S[st[j]+ii]) return false;
                    }
                }
                else {
                    C[j] = true, st[j] = p;
                }
                 p += ll[j];
            }
        }
    }
 
    return true;
}
 
inline bool dfs1(int, int);
inline bool dfs2(int, int, int);
bool dfs2(int i, int k, int max_ll){
    if (i == l[k]){
        ll[k] = 0; REP(i, l[k]) ll[k] += s[k][i] == Normal ? 1 : ll[s[k][i]];
        return dfs1(k + 1, max(max_ll, ll[k]));
    }
    else {
        DWN_N(s[k][i], k, -1){
            if (dfs2(i+1, k, max_ll)) return true;
        }
    }
    return false;
}
 
bool dfs1(int k = 0, int max_ll = 1){
 
    int t = max_ll; FOR(i, k, n) t *= _l[i];
    if (t < len) return false;
 
    if (k == n){
        return ll[k-1] == len && check();
    }
    else {
        DWN_1_N(l[k], _l[k], 0){
            if (dfs2(0, k, max_ll)) return true;
        }
    }
    return false;
}
 
int main(){
 
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    while (scanf("%d", &n) != EOF){
        DWN(i, n, 0) RD(_l[i]); RS(S); len = strlen(S); reverse(S, S + len);
        puts(dfs1() ? "Yes" : "No");
    }
}

Further discussion:

(不欣賞一下 ACrush 在 Marathon 版裡面發的代碼 么?。。)。

External link:

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4494