中文题,题意不多说。

本来感觉很像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)为右下方的矩阵

最新文章

  1. ABP理论学习之异常处理
  2. Sharepoint学习笔记—习题系列--70-576习题解析 -(Q138-Q140)
  3. tcpip的可靠性
  4. 《Thinking in Java》十七章_容器深入研究_练习12(Page484)
  5. MOB 短信验证
  6. Bata版本冲刺计划及安排
  7. oracle的数据库,随笔
  8. spark单机模式简单搭建
  9. dede 替换后台两个文件去广告
  10. java_访问权限修饰符
  11. 201521123095《java程序设计》第4周学习总结
  12. AppScan扫描结果分析及工具栏使用
  13. Mycat - 高可用与负载均衡实现,满满的干货!
  14. sql server 2008 express 安装的时提示“重启计算机失败&quot;
  15. php 获取当前在线用户数量
  16. authentication unavailable: no polkit agent available to authenticate action &#39;org.libvirt.unix.manage&#39;的问题解决
  17. dmidecode详解
  18. mongodb基本使用(一)
  19. prim和kruskal比较
  20. BZOJ4823 CQOI2017老C的方块(最小割)

热门文章

  1. EF查询生成的SQL
  2. webuploader上传插件
  3. js 的数据类型转换
  4. c# 海康威视 Winform播放mp4视频
  5. 拓展:return和print的使用时机
  6. (转)Qt Model/View 学习笔记 (六)——在views中选择数据项
  7. Spring execution 表达式
  8. sql之透视
  9. NSString常用方法
  10. springMVC上传图片