首页 > ACM题库 > HDU-杭电 > HDU 4051-Compress the String-回溯-[解题报告]HOJ
2015
04-16

HDU 4051-Compress the String-回溯-[解题报告]HOJ

Compress the String

问题描述 :

Dan is playing a game with Ben. Ben gives Dan a long string S, and Dan needs to compress S to a list or short strings: s[1], s[2], …, s[N]. S only contains lowercase letters. Each s[i] can contain lowercase letters and digits, but only digits between i+1 and N, inclusive, are allowed for s[i]. For example, when N = 4, allowed digits for s[2] will be ’3′ and ’4′.

In order to decompress such a list of strings into a single string, we’ll apply string decompress algorithm for each string one by one, in reverse order (from s[N] to s[1]). The decompressing algorithm for a string is easy: just replace each digit in the string by the corresponding decompressed string with that digit as index. That is to say, for digit i in the string, it will be replaced by the decompressed string s[i]. Because we are applying decompressing algorithm in reverse order, s[i] will always be decompressed before it is used to replace a digit in other strings. When all the strings are decompressed, the decompressed string of s[1] will be the final result. If the decompressing result is S, we say S can be compressed to this list of strings.

Now Ben decides the number of short strings Dan can use (N), as well as the length limit for each short string. Dan needs to decide whether it is possible to compress S to N short strings under this limit.

输入:

There are multiple test cases (no more than 150). For each case, there will be three lines. The first line gives an integer N (1 ≤ N ≤ 4), which is the number of short strings Dan can use. The second line gives N integers L[1], … L[N] (1 ≤ L[i] ≤ 4), which means the length of string s[i] should be at most L[i]. The third line gives the string S. The length of S will be between 1 and 500, inclusive. S will only contain lowercase letters.

输出:

There are multiple test cases (no more than 150). For each case, there will be three lines. The first line gives an integer N (1 ≤ N ≤ 4), which is the number of short strings Dan can use. The second line gives N integers L[1], … L[N] (1 ≤ L[i] ≤ 4), which means the length of string s[i] should be at most L[i]. The third line gives the string S. The length of S will be between 1 and 500, inclusive. S will only contain lowercase letters.

样例输入:

1
1
aa
4
4 4 4 4
ttttttttttttttt

样例输出:

No
Yes


题意:题目给定了一种压缩方法,对于一个仅由小写字母组成的长串Str,我们可以用若干小串s[1],s[2]…,s[N],来表示它,其中s[i]中只包含小写字母和[i+1,N]的整数,解压的时候按从s[N]到s[1]的顺序解压,解压s[i]时用s[k]来替换s[i]中的数字k,最终s[1]就是Str。现在给定Str,N及s[1],s[2]…s[N]的最大程度,问Str能否用这种压缩方法来表示

解法:搜索加剪枝,按从s[N]到s[1]的顺序来构造,对于每个s[i]构造一组模糊解,即只确定它的每一位是字符还是某个数字,全部构造完之后代入Str验证。还有一些剪枝比方说如果在目前已构造的串的前提下若生成串最长也无法达到Str则回溯,若目前构造的串串长已经超过Str则回溯之类之类的 还有一个比较诡异的地方:我代码的某个地方如果交换一下搜索顺序则会从AC变成WA…
代码:
#include <stdio.h>
#include <string.h>
#include <map>
#include <algorithm>
using namespace std;
char ss[4][10], str[600];
int l[5], c[4], n, mul[10], len, cn;
int maxl[5];
char stmp[10];
bool pd(int x);
int a[30], stri;
bool check(int ssx){
    int i, x;
    for (i = 0; ss[ssx][i]; i++){
        if (ss[ssx][i] < 10){
            if (!check(ss[ssx][i])){
                return false;
            }
        }else{
            x = ss[ssx][i];
            if (a[x] == -1){
                a[x] = str[stri];
            }
            if (a[x] != str[stri]) return false;
            stri++;
        }
    }
    return true;
}
bool wk(int x, int p){
    int i;
    if (l[x] > len) return false;
    if (p == c[x]){
        maxl[x] = max(maxl[x + 1], l[x]);
        return pd(x – 1);
    }
    for (i = x + 1; i < n; i++){
        l[x] += l[i];
        ss[x][p] = i;
        if (wk(x, p + 1)) return true;
        l[x] -= l[i];
    }
    ss[x][p] = cn++;
    l[x]++;
    if (wk(x, p + 1)) return true;
    cn–;
    l[x]–;
    ss[x][p] = 0;
    if (wk(x, c[x])) return true;
    return false;
}
bool pd(int x){
    if (mul[x] * maxl[x + 1] < len){
        return false;
    }
    if (x < 0){
        if (l[0] != len) return false;
        memset(a, -1, sizeof(a));
        stri = 0;
        return check(0);
    }
    l[x] = 0;
    if (wk(x, 0)) return true;
    return false;
}
map<char, int> mp;
int main(){
    int i, s, ss;
    while (scanf(“%d”, &n) != EOF){
        s = 1;
        for (i = 0; i < n; i++){
            scanf(“%d”, &c[i]);
            s += c[i] – 1;
        }
        ss = 0;
        mul[0] = c[0];
        for (i = 1; i < n; i++){
            mul[i] = mul[i - 1] * c[i];
        }
        l[n] = 1;
        maxl[n] = 1;
        scanf(“%s”, str);
        mp.clear();
        for (i = 0; str[i]; i++){
            if (mp.count(str[i]) == 0){
                mp[str[i]] = 1;
                ss++;
            }
        }
        if (ss > s){
            printf(“No\n”);
            continue;
        }
        len = strlen(str);
        if (len <= s){
            printf(“Yes\n”);
            continue;
        }
        cn = 10;
        if (pd(n – 1)){
            printf(“Yes\n”);
        }else{
            printf(“No\n”);
        }
    }
    return 0;
}

参考:http://capayoho.blog.163.com/blog/static/200037195201111160275732


  1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  4. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.