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. 改变搜索顺序。。(以对有解的情况下尽可能发现正解。。这剪枝一向很能打不是么？。 。。)。。

（居然这就过了。。可见数据还是弱。。）

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

Posted by xiaodao
Category: ZOJ