当前位置:网站首页>[2018 Blue Bridge Cup group B final] e-building blocks

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

2020-11-13 00:27:45 Fool_ One

Answer key

   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[0][1][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;
}

 

版权声明
本文为[Fool_ One]所创,转载请带上原文链接,感谢