10pts只对最后一个点求调
查看原帖
10pts只对最后一个点求调
983802
temp142857楼主2024/4/21 22:42
#include <bits/stdc++.h>

using ll = long long;

void solve(){
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> g(n);
    for(int i = 0; i < n; i++){
        std::cin >> g[i];
    }
    std::vector h(n, std::vector<int>(m, 0));// 悬线
    std::vector l(n, std::vector<int>(m, 0));// l[i][j] 为悬线高度大于等于h[i][j]的连续块最左端的位置.
    std::vector dp(n, std::vector<ll>(m, 0));//dp[i][j]表示以第i行第j列为右下角的矩形的数量
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(g[i][j] == '*') continue;
            h[i][j] = 1;
            if(i > 0 && g[i - 1][j] == '.') h[i][j] += h[i - 1][j];

        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 1 ; j < m; j++){
            if(h[i][j - 1] < h[i][j]){
                l[i][j] = j;
            }
            else if(h[i][j - 1] == h[i][j]){
                l[i][j] = l[i][j - 1];                
            }
            else{
                int k = j - 1;
                while(k >= 0 && h[i][k] >= h[i][j]){
                    k = l[i][k] - 1;
                }
                k++;
                l[i][j] = k;
            }
        }
    }

    ll ans = 0;
    
    for(int i = 0; i < n; i++){
        dp[i][0] = h[i][0];
        for(int j = 1; j < m; j++){
            if(g[i][j] == '*') continue;
            if(h[i][j] >= h[i][j - 1]){
                dp[i][j] = dp[i][j - 1] + h[i][j];
            }  
            else{// 找到第一个h小于h[i][j]的位置k
                int k = j - 1;
                while(k >= 0 && h[i][j] <= h[i][k]){
                    k = l[i][k] - 1;
                }
                dp[i][j] = (j - k) * h[i][j];
            }
        }
    }
    for(int i =0; i < n;i++){
        for(int j = 0; j< m; j++){
            ans += dp[i][j];
            // std::cout << dp[i][j] << " ";
        }
        // std::cout << '\n';
    }
    std::cout << ans << '\n';
}
int main() {

    int t = 1;
    // std::cin >> t;
    while(t--) solve();

    return 0;
}
2024/4/21 22:42
加载中...