[杂题]FZU2190 非提的救赎

中文题，题意不多说。

本来感觉很像dp

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

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

 1 //#include <bits/stdc++.h>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cctype>
 6 #include <climits>
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <cmath>
10 using namespace std;
11 typedef long long LL;
12 #include <queue>
13 
14 struct node
15 {
16     int val, cnt;
17 }S[2005];
18 int val[2005][2005];
19 char mp[2005][2005];
20 int main()
21 {
22     int n, m;
23     while(~scanf("%d%d", &n, &m))
24     {
25 //        memset(val, 0, sizeof(val));
26         for(int i=1;i<=n;i++)
27         {
28             val[i][0]=0;
29             scanf("%s", mp[i]+1);
30             for(int j=1;j<=m;j++)
31             {
32 //                cin>>mp[i][j];
33                 val[i][j]=(mp[i][j]=='w')? (val[i][j-1]+1):0;
34             }
35         }
36         LL ans=0;
37         for(int j=1;j<=m;j++)
38         {
39             LL sum=0;
40             int head=0;
41             for(int i=1;i<=n;i++)
42             {
43                 node t;
44                 t.val=val[i][j], t.cnt=1;
45                 while(head && t.val<=S[head-1].val)
46                 {
47                     head--;
48                     sum-=S[head].val*1LL*S[head].cnt;
49                     t.cnt+=S[head].cnt;
50                 }
51                 sum+=t.val*1LL*t.cnt;
52                 S[head++]=t;
53                 ans+=sum;
54             }
55         }
56         printf("%I64d
", ans);
57     }
58     return 0;
59 }

FZU 2190

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

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