Алгоритм подсчета количества подгрид, которые содержат все буквы [закрыто] ⇐ C++

[Anonymous]

cses - все буквы подсчеты I < /p>

Вам дают сетку букв. Ваша задача состоит в том, чтобы вычислить количество Square подгрид, которые содержат все буквы. Буквы являются первыми заглавными буквами KKK. < /P>
После этого есть строки NNN, которые описывают сетку. Каждая строка имеет буквы nnn. < /P>
output < /h1>
Распечатайте количество субгридов.

Код: Выделить всё

1 ≤ n ≤ 3000

[*]1 ≤ k ≤ 26

Пример
input:
5 3
ABBBC
BBBBC
BCAAA
AAAAA
AAAAA
< /code>
output: < /p>
15
< /code>
< /blockquote>
Я нашел решение, которое равно O (k n 2 < /sup>), где k-это размер алфавита, а n-размер сетки, но он работает слишком медленно. PrettyPrint-Override ">#include
#include

using namespace std;

int n, k;
const int MAXN = 3001;

int grid[MAXN][MAXN];

int ans[MAXN][MAXN];

int dp[MAXN];
int tmp[MAXN];

long long fin;

int main() {

cin >> n >> k;

for (int i=1; i tmp;
tmp -='A';
grid[j] = tmp;
}
}

for (int l=0; l

Подробнее здесь: https://stackoverflow.com/questions/797 ... ll-letters