[杂题]FZU2190 非提的救赎

时间：2022-01-24 00:13:13

中文题，题意不多说。

本来感觉很像dp

其实只要从上到下维护单调性就好了

坑是......这个oj......用cin很容易TLE......

 //#include <bits/stdc++.h>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cctype>

 #include <climits>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 typedef long long LL;

 #include <queue>

 struct node

 {

     int val, cnt;

 }S[];

 int val[][];

 char mp[][];

 int main()

 {

     int n, m;

     while(~scanf("%d%d", &n, &m))

     {

 //        memset(val, 0, sizeof(val));

         for(int i=;i<=n;i++)

         {

             val[i][]=;

             scanf("%s", mp[i]+);

             for(int j=;j<=m;j++)

             {

 //                cin>>mp[i][j];

                 val[i][j]=(mp[i][j]=='w')? (val[i][j-]+):;

             }

         }

         LL ans=;

         for(int j=;j<=m;j++)

         {

             LL sum=;

             int head=;

             for(int i=;i<=n;i++)

             {

                 node t;

                 t.val=val[i][j], t.cnt=;

                 while(head && t.val<=S[head-].val)

                 {

                     head--;

                     sum-=S[head].val*1LL*S[head].cnt;

                     t.cnt+=S[head].cnt;

                 }

                 sum+=t.val*1LL*t.cnt;

                 S[head++]=t;

                 ans+=sum;

             }

         }

         printf("%I64d\n", ans);

     }

     return ;

 }

FZU 2190

用val[i][j]记录(i, j)前方连续的w的数量

维护以(i, j)为右下方的矩阵

相关文章