Мобильная версия
Итак, Я пытаюсь решить задачу динамического программирования, где у меня есть эта таблица операций.
У меня есть, скажем, такая последовательность: 2⊕2⊕2⊕2⊕1⊕3 = 1, и я хочу, чтобы оно было равно 1.
В этой последовательности нет круглых скобок, поэтому возможны несколько порядков вычисления. Программа должна определить, существует ли такой порядок операций (с использованием круглых скобок), который соответствует ожидаемому результату. Например, одна из допустимых круглых скобок для приведенной выше последовательности:
((((2⊕2)⊕2)⊕(2⊕1))⊕3) = 1
Нам нужно найти самую левую скобку.
Я придумал решение, которое находит каждое отдельное решение, создавая таблицу dp и вычисляя каждая подпоследовательность и ее значение. Однако это крайне неэффективно, а для больших входных данных требуется очень много времени. Как я могу сделать так, чтобы это происходило как можно быстрее?
Ниже приведена соответствующая часть кода
#include
#include
#include
using namespace std;
// Structure to store the value and the corresponding expression
struct Result {
int value;
string expression;
};
int main() {
// Optimization to improve the performance of cin/cout (found on the course page)
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m; // Reads n (dimension of the table) and m (length of the sequence).
// Reads the operation table
vector table(n, vector(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> table[j];
}
}
// Reads the sequence of integers
vector sequence(m);
for (int i = 0; i < m; ++i) {
cin >> sequence;
}
// Reads the expected result
int expectedResult;
cin >> expectedResult;
// Initializes the DP (dynamic programming) table
vector dp(m, vector(m));
// Fills the base cases (intervals of size 1)
for (int i = 0; i < m; ++i) {
dp.push_back({sequence, to_string(sequence)});
}
// Fills the intervals of size greater than 1
for (int len = 2; len
Подробнее здесь: https://stackoverflow.com/questions/792 ... ming-issue
