fzoj Problem 2190 非提的救赎 【单调栈】「终于解决」

大家好，欢迎来到IT知识分享网。

题目链接：fzoj Problem 2190 非提的救赎

Problem 2190 非提的救赎
Accept: 106 Submit: 312
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
正如你所知道从前有一个人叫s_sin，她拥有着坐拥三千舰狼的梦想！然而天不遂人愿当她踏进hentai collection的大门之后，现实让她领略到了无情。身为一个坚强的妹子，她知道即使出门大破，即使十一连抽全是R，也要坚信着“玄不救非，氪不改命”，而自己是一个欧白这样最初的信仰！

有一天s_sin率领着她的舰狼们到达了某海峡，以一个N*M的矩阵表示，每一个元素为w或者b。其中b为暗礁，暗礁上是不允许有舰狼存在的。而s_sin也相信着一个道理，那就是只有把她的舰狼们组成矩形，她才能有足够的信仰在打败了最终boss之后捞到心仪的新舰狼。请问s_sin有多少种获取足够信仰的方法？（即在N*M的矩阵中有多少个全部由w组成的子矩形）

Input
输入第一行为一个正整数N，M表示有N行M列的矩阵。

接下来N行每行有M个字母为b或者w，如描述中所述。

Output
求N*M的矩阵中有多少个全部由w组成的子矩形。

Sample Input
2 3
bbb
www
2 2
bw
wb Sample Output
6
2 Hint
1<=M,N<=2000
Source
福州大学第十二届程序设计竞赛

思路： 我们枚举每一行，把第j列当做是第j根柱子，记W[j] = (1, j)到(i, j)的连续长度。从左向右推——考虑以(i, j)为右下角的矩形个数dp[i][j]，我们先找到以W[j]为宽的最大矩形A，用单调栈快速找到矩形左边界l，个数就为 矩形A格子数目 + dp[i][j – l]。

AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define CLR(a, b) memset(a, (b), sizeof(a))
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int MAXN = 1e4 +10;
const int INF = 0x3f3f3f3f;
char str[2010][2010];
pii Stack[2010]; int d[2010];
LL dp[2010];
int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF) {
        for(int i = 1; i <= n; i++) {
            scanf("%s", str[i]+1);
        }
        for(int j = 1; j <= m; j++) d[j] = 0;
        LL ans = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(str[i][j] == 'w') {
                    d[j]++;
                }
                else {
                    d[j] = 0;
                }
                dp[j] = 0;
            }
            int top = 0; int l;
            for(int j = 1; j <= m; j++) {
                while(top && Stack[top-1].fi >= d[j]) top--;
                Stack[top++] = pii(d[j], j);
                if(top == 1) {
                    l = Stack[top-1].se;
                }
                else {
                    l = Stack[top-1].se - Stack[top-2].se;
                }
                int id = Stack[top-1].se;
                if(d[id] == 0) continue;
                dp[id] = 1LL * l * Stack[top-1].fi + dp[id - l];
                ans += dp[id];
                //cout << dp[id] << endl;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}