динамическое программирование — как сделать запоминание в следующем коде c ++
На самом деле я пытаюсь решить проблему SPOJ:
[SPOJ] http://www.spoj.com/problems/SQRBR/ . Я пришел с уверенностью, чтобы решить это, но я не понимаю, как сделать запоминание. Любое предложение о том, как запоминать данную проблему, будет полезным. мой код дает правильный ответ, но он дает TLE в спой Вот мой код:
#include <iostream>
#include <cstdio>
using namespace std;
void balancedParen(int n, int open, int position, int close, char str[], string s, long long int &counter) {
if(close == n) {
str[pos] = '\0';
printf("%s\n", str);
counter++;
return;
}
if(s[position] == '(' ) {
if(open <= n-1) {
str[position] = '(';
balancedParen(n, open+1, position+1, close, str, s, counter);
}
} else {
if(open < n) {
str[position] = '(';
balancedParen(n, open+1, position+1, close, str, s, counter);
}
if(open > close) {
str[position] = ')';
balancedParen(n, open, position+1, close+1, str, s, counter);
}
}
return ;
}
int main() {
int a[100], n, k, i;
long long counter = 0;
int testCases;
scanf("%d", &testCases);
while(testCases--) {
scanf("%d", &n);
scanf("%d", &k);
char str[100];
string s = "..........................................................................";
for(i = 0; i < k; i++) {
scanf("%d", &a[i]);
s[a[i]-1] = '(';
}
balancedParen(n, 0, 0, 0, str, s, counter);
printf("%lld\n", counter);
counter = 0;
}
return 0;
}
Решение
Я могу думать об одной относительно простой и, возможно, значительной оптимизации.
Во-первых, вместо ссылки «counter» сделайте его возвращаемым значением функции. Выслушай меня немного здесь.
Теперь скажите, что вам даны позиции «1, 7, 15». Вместо рекурсивного перехода «1, 2, 3, 4, 5, 6, 7», вы можете быть немного хитрее и перейти к 7 за один шаг.
Вам просто нужно посчитать количество перестановок, которое можно использовать для перехода от 1 до 7, для каждого возможного числа открывающих паренов (в данном случае 3, 4, 5 и 6)
Например, сколько существует способов, чтобы иметь 3 вводных парена между 1 и 7?
[[[]]]
[[][]]
[][][]
[[]][]
[][[]]
5 перестановок (если я не пропустил одну). Так что вы можете добавить 5*balancedParen(n, open+3, position+6, close+3, str, s, counter) к вашему результату. И сделайте то же самое для 4, 5 и 6 вводных паренов.
Конечно, вам нужно написать другую функцию (рекурсивный подход кажется самым простым), чтобы найти это число «5». Но преимущество в том, что общее количество вызовов функций теперь (calls to get from 1 to 7) + (calls to get from 7 to 15), скорее, чем (calls to get from 1 to 7) * (calls to get from 7 to 15),
Вот некоторый код, который должен работать, используя алгоритм, который я описал:
int countPermutations(int unclosed, int length, int toOpen)
{
if (toOpen > length) // impossible to open this many, not enough length
return 0;
int toClose = length-toOpen;
if (toClose - toOpen > unclosed)
return 0; // No possibilities; not enough open parens to fill the length
if (toOpen == 0 || toOpen == length)
return 1; // Only one possibility now
int ret = 0;
if (toOpen > 0) // Count permutations if we opened a paren here
ret += countPermutations(unclosed+1, length-1, toOpen-1);
if (unclosed > 0) // Count permutations if we closed a paren here
ret += countPermutations(unclosed-1, length-1, toOpen);
return ret;
}
int countNLengthSolutions(int n, int unclosed, int position, int *positions, int remainingPositions)
{
if (n % 2 != 0)
return 0; // must be a length divisible by 2
if (position > n)
return 0;
if (n-position < unclosed)
return 0; // too many open parens, no way to complete within length
if (remainingPositions == 0)
{
// Too many open parens to close by the time we get to length N?
if ((n - position) < unclosed)
return 0;
else // Say we have 4 open and a length of 10 to fill; we want (10-4)/2 = 3 more open parens.
return countPermutations(unclosed, n-position, (n-position - unclosed)/2);
}
else
{
int ret = 0;
int toFill = *positions - position - 1;
for (int openParens = 0; openParens <= toFill; openParens++)
{
int permutations = countPermutations(unclosed, toFill, openParens);
if (permutations > 0)
ret += permutations*countNLengthSolutions(n, unclosed+(2*openParens-toFill)+1, position+toFill+1, positions+1, remainingPositions-1);
}
return ret;
}
}
У меня может быть ошибка где-то, я действительно не тратил время на проверку, но я убедился, что она работает для всех примеров ввода.
Другие решения
Других решений пока нет …