题目大意:

在矩阵(只有52种字符)中找出所有不包含重复字符的子矩阵个数

#include <bits/stdc++.h>
#define ll long long
using namespace std; int n,m;
char G[][];
int lr[][], ud[][];
int pos[], len[]; int main()
{
while(~scanf("%d%d",&n,&m)) {
for(int i=;i<=n;i++) scanf("%s",G[i]+);
for(int i=;i<=n;i++) {
memset(pos,,sizeof(pos));
for(int j=;j<=m;j++) {
lr[i][j]=min(lr[i][j-]+,j-pos[G[i][j]-'A']);
pos[G[i][j]-'A']=j;
}
}
for(int j=;j<=m;j++) {
memset(pos,,sizeof(pos));
for(int i=;i<=n;i++) {
ud[i][j]=min(ud[i-][j]+,i-pos[G[i][j]-'A']);
pos[G[i][j]-'A']=i;
}
}
/* 若固定右下角
且只看一个因素(长度或高度),忽略另一个因素
则高度(长度)多大 划分方案就有多少种
如高度(长度)为3 划分方案就恰好3种 用一个极端的样例说明
ABC 固定C为右下角的划分方案只有三种
即 C、BC、ABC 三种
*/
ll ans=;
for(int j=;j<=m;j++) {
memset(len,,sizeof(len));
for(int i=;i<=n;i++) { /// 求以G[i][j]为右下角的划分方案 for(int k=;k<lr[i][j];k++) { /// 在i行 j列(右界)向左k长度
len[k]=min(len[k]+,ud[i][j-k]); // 控制高度
/// 由i-1行扩展而来有 len[k]+1 种划分
/// 由i行j-k列(左界)控制的 ud[i][j-k] 高度,超过这个高度会有重复
// 不用纠结在左右界只间有更小的高度 这个问题会在 长度控制 时被制约到
/// 两者中取小 控制不重复 if(k) len[k]=min(len[k],len[k-]); // 控制长度
/// k长度的划分 不可能多于 k-1长度的划分
ans+=len[k];
} for(int k=lr[i][j];k<;k++) len[k]=;
}
}
printf("%lld\n",ans);
} return ;
}

最新文章

  1. 设计模式(十)组合模式(Composite Pattern)
  2. 基于类的命令行notebook的实现
  3. BLOG搬家
  4. linux查看磁盘io的几种方法
  5. Windows server 2008 r2搭建FTP服务器
  6. Xenomai
  7. 《day09---继承-抽象类-接口》
  8. Python教程:[69]strip()函数详解
  9. VS开发工具 不会在异常的地方停止的问题.
  10. 606. Construct String from Binary Tree
  11. c#中不同类中变量的引用方法
  12. 学习css之选择器优先级
  13. Java学习之软件安装
  14. vue组件详解——组件通信
  15. checkbox的使用总结,判断是否选中
  16. 使用PHPExcel实现Excel文件的导入和导出(模板导出)
  17. tracert traceroute
  18. 利用 Express 托管静态文件
  19. @Scope注解设置创建bean的方式和生命周期
  20. HttpRequest中常见的四种Content-Type(转)

热门文章

  1. Java checked异常 和 RuntimeException
  2. kma 2019CSP前刷题记录
  3. Spring-Security (学习记录二)--修改为自己的登录页面
  4. random,time,sys,os,序列化模块
  5. C语言中static用法介绍
  6. Putty 两步代理访问互联网
  7. 剑指offer——19删除链表的节点
  8. 两个问题: 1、头文件重复包含 2、头文件加了ifndef条件预处理指令为什么还会定义
  9. licecap图片区域问题
  10. Git的故事