SPOJ смайлик вызов


Я попробовал этот spoj проблему и решить ее методом динамического программирования, но я был все время превышен лимит. Задача состоит в том, чтобы подсчитать количество вхождений подпоследовательности "КЭК" в каждой входной строке.

Некоторые люди в комментариях заявили, что им удалось сделать за o(n) времени. Я понятия не имею. может кто-нибудь дать мне идею? Вот моя динамического программирования.

#include<bits/stdc++.h>
using namespace std;
int dp(string s,int in,int len,int pos){
    if(in == len){
        return 0;
    }
    if(pos == 0){
        if(s[in] == 'K'){
            return dp(s,in+1,len,1)+dp(s,in+1,len,0);
        }
        return dp(s,in+1,len,0);
    }
    if(pos == 1){
        if(s[in] == 'E'){
            return dp(s,in+1,len,2)+dp(s,in+1,len,1);
        }
        return dp(s,in+1,len,1);
    }
    if(pos == 2){
        if(s[in] == 'K'){
            return 1+dp(s,in+1,len,2);
        }
        return dp(s,in+1,len,2);
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int l = s.size();
        int k = dp(s,0,l,0);
        cout<<k<<endl;
    }
    return 0;
}


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

Вы повторно копировать параметр строку при каждом рекурсивном вызове. Что будет съедать ваше время.

Похоже, что вы программируете в автомат с тремя состояниями.

Функция имеет три отделения для государства 0,1,2, но не имеют общего кода (проверка условия) и вы знаете номер, когда вы делаете вызов. Итак, сделать три отдельные функции.

Строки знает свой размер. Вам не нужно проходить отдельно. В std::string_view хорошо грызть далеко от концов, так использовать, что и вам не нужно пройти in.

Я предлагаю добавлять статический счетчик, так что вы можете увидеть, как много рекурсивные вызовы осуществляются!

Не пишите using namespace std;.

Вы можете, однако, в cpp-файл (не файл) или внутри функции, поставить индивидуальные using std::string; и т. д. (См. СФ.7.)


Идея о том, как сделать это в (Н)

int f (const std::string& s)
{
std::vector<int> b;
int n {0};
for (auto c : s) {
if (c=='E') b.push_back(n);
else if (c=='K') ++n;
}
int sum {0};
for (auto i : b)
sum += i*(n-i);
return sum;
}

Строке только один раз. Это ключ к его (н). Вместо рекурсии я нажимаем значение на стеке и продолжайте с первой половины следующей идти. После достижения конца строки, всплывающие каждое значение и полный расчет. (Я сделал ФИФО и не ЛИФО, но это неважно) можно увидеть, чтобы преобразовать это в рекурсии вызов будет идти туда, где push_back здесь, минуя остальные строки и N до сих пор. Натяжной кадр стека помнит тока N в этой точке. Когда конец строки и все начинается вернувшись, он возвращает общее и конечное значение н; он добавляет свою собственную терминологию и возвращает к предыдущему.

Чтобы сделать это быстрее, использовать статический буфер размера (так как вы сказали максимальный размер все) и тоже использовать более быструю функцию чтения.

1
ответ дан 18 мая 2018 в 08:05 Источник Поделиться


int dp(string s,int in,int len,int pos){

Где комментарии, чтобы объяснить значения переменных? Мы вынуждены перепроектировать их.


    if(in == len){
return 0;
}
if(pos == 0){
if(s[in] == 'K'){
return dp(s,in+1,len,1)+dp(s,in+1,len,0);
}
return dp(s,in+1,len,0);
}
if(pos == 1){
if(s[in] == 'E'){
return dp(s,in+1,len,2)+dp(s,in+1,len,1);
}
return dp(s,in+1,len,1);
}
if(pos == 2){
if(s[in] == 'K'){
return 1+dp(s,in+1,len,2);
}
return dp(s,in+1,len,2);
}
}

Это не динамическое программирование. Динамический программный подход к этой проблеме должен работать на следующей основе:


Учитывая структуру S в которой обобщены префикс strи следующий символ chнам нужно вывести структуру S' в которой обобщены префикс str + ch.

У нас есть несколько простых выводов:


  • S должны предоставить нам номер нужной подпоследовательности, потому что в конце ДП перспективе мы будем иметь только S соответствует всей строке. Поэтому он имеет поле, которое мы можем назвать kek.

  • Если ch ни 'E' ни 'K' тогда S' = S.

  • Если ch != 'K' тогда S'.kek = S.kek.

  • Если ch == 'K', S должны предоставить нам некоторые возможности узнать, насколько больше S'.kek должно быть, чем S.kek. Очевидно, что должно быть число КЭК подпоследовательностей, заканчивающихся ch- количество ки подпоследовательностей в str.

Вы должны быть в состоянии нести это мышление, чтобы заполнить весь список отраслей, нуждающихся в S и логика, чтобы обновить их при чтении 'E' и при чтении 'K'.

2
ответ дан 26 марта 2018 в 08:03 Источник Поделиться

Возможно, вы преувеличиваете. Самое простое решение-это:

int sum = 0;
for(int i=0;i<length;i++) {
if (input[i] == 'E') {
sum += numberOfKBefore[i] * numberOfKAfter[i];
}
}

и динамического программирования часть только заполнить numberOfKSoFar массив с количеством "к".

1
ответ дан 18 мая 2018 в 01:05 Источник Поделиться