Форум программистов, компьютерный форум CyberForum.ru

Запаковка - C++

Восстановить пароль Регистрация
 
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
25.10.2010, 19:26     Запаковка #1
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Гамма

Билл пытается компактно представить последовательность заглавных латинских букв от 'A' до 'Z', с учетом повторяющихся последовательностей в ней. Например, возможный способ представить последовательность AAAAAAAAAABABABCCD - есть 10(A)2(BA)B2(C)D. Билл ввел формальное понятие упакованной последовательности так:
• Последовательность, содержащая один символ из диапазона 'A'..'Z' считается упакованной последовательностью. Ее распаковка возвращает тот же символ.
• Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Причем, если результатом распаковки S является S', а Q - Q', то SQ распаковывается в S'Q'.
• Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное целое число, большее 1. Если S распаковывается в S', то X(S) распаковывается в S', повторенную X раз.

Согласно этому определению легко распаковать любую запакованную последовательность. Но Билл более заинтересован в обратной операции. Он хочет запаковать данную последовательность так, чтобы результирующая запакованная последовательность содержала как можно меньше символов (включая цифры и скобки).

Ввод
Одна строка, состоящая не менее, чем из одного и не более чем из 100 символов в диапазоне 'A'..'Z'.
Вывод
Число - длину кратчайшего из вариантов запаковки исходной последовательности.

Ввод 1 Ввод 2
AAAAAAAAAABABABCCD NEERCYESYESYESNEERCYESYESYES
Вывод 1 Вывод 2
12 14
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mayonez
 Аватар для Mayonez
379 / 271 / 20
Регистрация: 26.12.2009
Сообщений: 875
25.10.2010, 21:15     Запаковка #2
Цитата Сообщение от Hardcore Посмотреть сообщение
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Гамма
а что это значит?
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
26.10.2010, 12:23  [ТС]     Запаковка #3
Это лимит времени на компиляцию и объем экзэшника.
easybudda
26.10.2010, 12:33
  #4

Не по теме:

Цитата Сообщение от Hardcore Посмотреть сообщение
Это лимит времени на компиляцию и объем экзэшника.
0.00000003125 миллисекунды и 0,000000000023669 килобайт, да ещё и с гамма-сложностью? Это чё за марсианский девайс такой?

Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
26.10.2010, 13:50     Запаковка #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <fstream>
#include <string>
 
using namespace std;
 
ofstream cout("output.txt");
ifstream cin("input.txt");
 
int dp[200][200]; // [start][len]
string s;
 
const int inf = 987654321;
 
int numberLen(int n)
{
    if(n <= 9)
        return 1;
    else
        return 2;
}
 
bool good(int start, int L, int len)
{
    for(int i = L; i < len; i++)
        if(s[start+i] != s[start+i%L])
            return false;
    return true;
}
 
int f(int start, int len)
{
    if(dp[start][len] == 0)
    {
        if(len == 1)
            dp[start][len] = 1;
        else
        {
            dp[start][len] = inf;
            for(int L = 1; L <= len-1; L++)
                dp[start][len] = min(dp[start][len],f(start,L)+f(start+L,len-L));
 
            for(int L = 1; L <= len/2; L++)
                if(len % L == 0)
                    if(good(start,L,len))
                            dp[start][len] = min(dp[start][len], numberLen(len/L) + 2 + f(start,L));
        }
    }
    return dp[start][len];
}
 
int main()
{
    cin >> s;
    cout << f(0,s.size());
}
Yandex
Объявления
26.10.2010, 13:50     Запаковка
Ответ Создать тему
Опции темы

Текущее время: 07:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru