[杂题]FZU2190 非提的救赎
2024-09-16 07:24:48
中文题,题意不多说。
本来感觉很像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)为右下方的矩阵
最新文章
- ABP理论学习之异常处理
- Sharepoint学习笔记—习题系列--70-576习题解析 -(Q138-Q140)
- tcpip的可靠性
- 《Thinking in Java》十七章_容器深入研究_练习12(Page484)
- MOB 短信验证
- Bata版本冲刺计划及安排
- oracle的数据库,随笔
- spark单机模式简单搭建
- dede 替换后台两个文件去广告
- java_访问权限修饰符
- 201521123095《java程序设计》第4周学习总结
- AppScan扫描结果分析及工具栏使用
- Mycat - 高可用与负载均衡实现,满满的干货!
- sql server 2008 express 安装的时提示“重启计算机失败";
- php 获取当前在线用户数量
- authentication unavailable: no polkit agent available to authenticate action &#39;org.libvirt.unix.manage&#39;的问题解决
- dmidecode详解
- mongodb基本使用(一)
- prim和kruskal比较
- BZOJ4823 CQOI2017老C的方块(最小割)