2015
04-16

# 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

#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;
}

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.