# [2018 Blue Bridge Cup group B final] e-building blocks

2020-11-13 00:27:45 This question examines the classical algorithm , But I'm still too good ..., Can not do /(ㄒoㄒ)/~~.

The correct solution should be dp + Prefixes and optimizations , Only solution n == 1 Or violence dp It's going to be overtime , How do you see it ?

dp： f[i][j][k] It means the first one i Layer in [j, k] The total number of building blocks in the interval ,dp The equation is obviously f[i][j][k] = f[i][j][k] + f[i - 1][x][y]; among [j, k] There is no place for an interval to be placed , It's violence dp How to do it , The time complexity is \$O(n^5)\$.

Prefixes and optimizations ：

In the above illustration , The first i - 1 layer f[i - 1][x][y] namely [x, y] This part can obviously be prefixed and optimized , It only took \$O(1)\$ The complexity of time can be completed , The formula of two-dimensional prefix and initialization is ：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j], To solve the submatrix is ：s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1], If you are not familiar with it, you can draw a picture and push it , Easier to understand .

The time complexity is \$O(n^3)\$, You can do it .

```#include <iostream>
using namespace std;

typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int n, m;
LL f[N][N][N];
LL s[N][N], c[N][N];

//  The prefix and
void get_presum(int i)
{
//  The prefix of a square and , From the  1  Start
for (int j = 1; j <= m; ++j) {
for (int k = 1; k <= m; ++k) {
s[j][k] = (s[j - 1][k] + s[j][k - 1] - s[j - 1][k - 1] + f[i][j][k]) % mod;
}
}
}

//  Submatrix
int submatrix(int x1, int y1, int x2, int y2)
{
return (s[x2][y2] - s[x1 -  1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]) % mod;
}

int main()
{
cin >> n >> m;
char str[N];
//  Bottom up （ Turn it upside down ）
for (int i = n; i; --i) {
cin >> str + 1;
for (int j = 1; j <= m; ++j) {
c[i][j] = c[i][j - 1]+ (str[j] == 'X');
}
}
f[m] = 1;
get_presum(0);
LL ans = 1;
// dp  Number of solutions per row
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int k = j; k <= m; ++k) {
if (c[i][k] - c[i][j - 1] == 0) {
//  Notice the subscript transformation  (1, k)  and  (j, m)
f[i][j][k] = (f[i][j][k] + submatrix(1, k, j, m)) % mod;
ans = (ans + f[i][j][k]) % mod;
}
}
}
get_presum(i);
}
cout << (ans + mod) % mod << endl;
return 0;
}```