Заполнение строки при минимальных затратах


Я решаю следующую задачу. Вот условие задачи:

Вам дана строка со специальными символами, например X***Y*Z. Ваша цель состоит, чтобы распечатать входной строки заполнять все символы в заданной строке.

Вы имеете право записать данные в строку в блоках фиксированного размера: посимвольно, вы можете написать прилегающих друг к другу блоков из одинаковых символов длиной 2, 3 ... N: X, XX, XXXи т. д. Например:

Блок: ХХ, применяются к позиции 2 в Х***Г*З => х*ХХУ*з

Это позволило переписать же персонажи:

Блок: ХХ, применять в положение " 0 " по х***Г*З => ХХ**Г*З

При выборе размера блока, который вы хотели бы использовать, скажем S "подготовка" расходы возникает: S * L, где L - некоторый входной сигнал постоянный.
Допустим, вы подобрали размер 2 (стоимость 2 * L), то вам позволено писать XX, YYи ZZ в данную строку.

Когда вы пишете блок данных в заданную строку, пишу затрат происходит - некоторых ввода константы C это не зависит от размера блока. Когда вы выберете какой-то блок длина, например 2вы должны заполнить все пробелы с помощью block_size = 2нельзя уменьшать или увеличивать ее в середине письма. Например, если вы пишете первый кусок данных в данную строку как XXпозже вы можете использовать YY и ZZ только. То же самое с другими размерами.

Ваша задача определить минимально возможную стоимость, чтобы заполнить все пробелы с учетом расходов на запись данных и подготовке блока.

Давайте рассмотрим пример, приведенный выше в деталях. Дана строка, X***Y*Z, L = 20, C = 10. Для каждого варианта существует множество вариантов, как заполнять бланки.

1) мы можем заполнить все пробелы с блоком размер 1 используя любые символы из {X, Y, Z}. Таким образом, общая стоимость составляет 1 * 20 (prepare a block of size 1) + 4 * 10 (fill 4 wildcards) = 60. Возможные результаты, есть много из них:

XYXZYXZ, XXXYYZZ ...

2) мы можем использовать block size = 2. Например: переписать X* С XX, ** С XX, Y* С YYобщая стоимость 2 * 20 (prepare the block of size 2) + 3 * 10 (perform 3 writing operations to fill all blanks), the total cost is 70.

Пример:

Решение 1

Инит: Х***Й*З

Шаг 1: напишите ХХ на 0 => ХХ**Г*З

Шаг 2: Напишите XX в 1 => ХХХ*Г*З

Шаг 3: напишите ый на 3 => XXXYY*з

Шаг 4: Напишите ЗЗ на 4 => XXXXYYZ

Мое решение довольно простое:

  1. предположим, длина блока данных равна M
  2. Попробуйте заполнить строку с помощью DFS
  3. Вычислить и стоимость обновления при необходимости
  4. Увеличение размера блока, Гото 1

Она работает довольно хорошо, но я интересно, если производительность может быть лучше?

Код:

#include <iostream>

using namespace std;

int N = 0;
int L = 0;
int K = 0;

const int max_length = 101;

const int max_value = 1000000;

char s[max_length];
char buf[max_length];

int min (int a, int b) {
  return a < b ? a : b;
}

int print_string(char d, int start, int d_size, int depth) {
  if (start >= N) return max_value;
  if (start + d_size > N) return max_value;

  for (int i = start; i < start + d_size; ++i) {
    if (buf[i] != '*' && buf[i] != d) return max_value;
  }

  if (start + d_size == N) return depth;

  for (int i = start; i < start + d_size; ++i) { buf[i] = d; }

  int res = max_value;

  for (int i = start; i < start + d_size; ++i) {
    int xc = print_string('X', i+1, d_size, depth+1);
    int yc = print_string('Y', i+1, d_size, depth+1);
    int zc = print_string('Z', i+1, d_size, depth+1);

    res = min(res, min (xc, min (yc, zc)));
  }

  for (int i = start; i < start + d_size; ++i) { buf[i] = s[i]; }

  return res;
}

int compute() {
  // we always can solve with m == 1, so there is no point in checking it
  // assuming that it is maximum cost
  int cost = N * K + 1 * L;

  for (int m = 2; m <= N; ++m) {
//    cout << "size " << m << '\n';

    int xc = print_string('X', 0, m, 1);
    int yc = print_string('Y', 0, m, 1);
    int zc = print_string('Z', 0, m, 1);

    const int steps = min(xc, min(yc, zc));

    const int cur = K * steps + L * m;

    if (cur < cost) {
      cost = cur;
    }
  }


  return cost;
}

int main(int argc, char* argv[]) {
  int T = 0;
  cin >> T;

  for(int t = 1; t <= T; ++t) {
    cin >> N;
    cin >> L;
    cin >> K;

    for (int i = 0; i < N; ++i) { cin >> s[i]; buf[i] = s[i]; }

    int res = compute();

    int exp = 0;
    cin >> exp;
    cout << "#" << t << " " << res << "; expected = " << exp << '\n';
  }
  return 0;
}

Образец данных:

7
48 10 10
XX****YY*X*ZXX****YY*X*ZXX****YY*X*ZXX****YY*X*Z
260
6 13 8
**X**Y
50
6 13 8
XXX**Z
50
6 13 8
XXX***
50
6 13 8
X*Y*X*
50
5 13 8
ZZZZZ
50
5 13 8
XYZYX
53


Комментарии
1 ответ

В первую очередь, проверив в пределах, если вы можете написать письмо или не может быть улучшена до O(1) по проверить, в моем случае я использовал letter_qty для этого.

Другое дело, что может улучшить ваше добавление кэша, потому что чем длиннее строка (и более *), то тем больше повторений вы делаете в рекурсивных вызовов. В моем случае я использовал cache для этого.

Только с этих 2 изменений, я думаю, что ваш код будет значительно улучшена.

Еще одно наблюдение заключается в том, что не надо стараться для каждого индекса пишу 3 буквы. Когда у нас есть шаблон, нужно только попробовать, используя буквы из предыдущего индекса и письмо, которое еще впереди (str[index + n]), потому что третья буква не имеет значение в этом диапазоне. Когда у нас нет шаблона, есть только 1 Выбор письмо, чтобы сделать.

Мое последнее замечание: если там "ничего так", не надо пытаться писать на нескольких индексов думать надо "оставить место" в случае, если у нас есть другой буквой "скоро". Это полностью отрезает ветвления в этих случаях, что в дальнейшем помогает в производительности. Я определил "долгий путь" как block_size * 2, как я уверен, что достаточно, но может быть и меньше.

Взял меня некоторое время, но не могу найти ничего, чтобы улучшить. Хотя мой код работает для тестов, больше тестов должно быть сделано, так как там могут быть некоторые ошибки. Ваш код мне понадобилось 12 лет, чтобы решить, не измерен мой, но его наверняка под 1С .

Вот мое собственное решение, со всеми этими идеями:

    #include <iostream>
#include <algorithm>

#include <vector>
#include <math.h>

using namespace std;

vector<int> next_letter;
vector<int> letter_qty[3];
vector<int> cache[3];
int block_size;
string str;

const int MAX = 1000000;

int solve(int index, char last_char);

int idx(char c) {
return c - 'X';
}

// O(1) check if we can write block_size times want character starting at str[index]
int solve2(int index, char want) {
if (letter_qty[idx(want)][index] != letter_qty[idx(want)][min(index + block_size - 1, (int)str.length() - 1)]) return MAX;

return solve(index + block_size, want);
}

//this is what truly speeds up the algorithm as it cuts branching if there "are not obstacles"
//the idea is that if we want to write an X, if there is no Y or Z "far ahead" (from index to index + block_size * 2), we can just write it instead of writing on all possible positions
bool obstaclesInTheWay (int index, char last_char) {
return index + block_size * 2 >= str.length() || last_char == '*' || letter_qty[idx(last_char)][index] != letter_qty[idx(last_char)][index + block_size * 2];
}

//index is where we are, last_char is the last_char used for writing. There is always at least block_size times the last_char before index. This way we avoid using a buffer to know what´s behind
int solve(int index, char last_char) {

if (index == str.length()) return 0;
if (index > str.length()) return MAX;

if (cache[idx(last_char)][index] != -1) return cache[idx(last_char)][index]; //avoid recalculating

int sol = MAX;

if (str[index] == '*') { // if there is wildcard, we can either use next letter to write or expand from lower indexes with last_char
sol = solve2(index, next_letter[index]);
} else { // if not, our only choice is to write with that letter
sol = solve2(index, str[index]);
if (last_char != str[index]) return cache[idx(last_char)][index] = sol + 1; // if that letter is not the same as last one, there is no sense in trying to expand from lower indexes
}

if (obstaclesInTheWay(index, last_char)) { // try using last_char in range [index - block_size + 1, index]
for (int i = max(index - (block_size - 1), 0); i <= index; i++) {
sol = min(sol, solve2(i, last_char));
}
}

return cache[idx(last_char)][index] = sol + 1;

}

int compute(int L, int C) {
int best_cost = str.length() * C + L; // always possible with size 1

for (block_size = 2; block_size <= str.length(); block_size++) {
int estimated_cost = ceil(str.length() / block_size) * C + L * block_size; // a lower bound of the cost, no sense in trying if lower bound will be greater than best
if (estimated_cost >= best_cost) continue;

for(int j = 0; j < 3; j++) {
fill(cache[j].begin(), cache[j].end(), -1); //clearing cache
}

int writings = solve(0, 'X');
best_cost = min(best_cost, writings * C + L * block_size);

if (writings >= MAX) break; // if its not possible to make with size block_size, won´t be possible with any greater size either
}

return best_cost;
}

//for each index we want to know the next letter ahead (not counting *)
void fillNextLetter () {
int idx = 0;

for (int i = 1; i < str.length(); i++) {
if (str[i] != '*') {
while(idx < i) {
next_letter[idx++] = str[i];
}
}
}

// for cases where the end is filled with *, we put any letter as next
while(idx < str.length()) {
next_letter[idx++] = 'X';
}
}

//we store for each letter, how many different letters appeared up to index i. With this, we can know if in a range there are only X (allowing *) or there is a Y or Z
void fillLetterQty () {
for (int j = 0; j < 3; j++) {
letter_qty[j][0] = 0;
for (int i = 1; i < str.length(); i++) {
letter_qty[j][i] = letter_qty[j][i - 1] + (str[i] != 'X' + j && str[i] != '*');
}
}
}

int main () {
int cases, L, C, N, expected;
cin >> cases;

for (int i = 1; i <= cases;i++) {
cin >> N >> L >> C;
cin >> str;

next_letter.resize(N);

for (int j = 0; j < 3; j++) {
letter_qty[j].resize(N);
cache[j].resize(N);
}

fillNextLetter();
fillLetterQty();

cin >> expected;
cout << "#" << i << " " << compute(L, C) << "; expected = " << expected << '\n';
}
}

1
ответ дан 21 марта 2018 в 04:03 Источник Поделиться