牛客集训第七场J /// DP
2024-09-06 11:08:46
题目大意:
在矩阵(只有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 ;
}
最新文章
- 设计模式(十)组合模式(Composite Pattern)
- 基于类的命令行notebook的实现
- BLOG搬家
- linux查看磁盘io的几种方法
- Windows server 2008 r2搭建FTP服务器
- Xenomai
- 《day09---继承-抽象类-接口》
- Python教程:[69]strip()函数详解
- VS开发工具 不会在异常的地方停止的问题.
- 606. Construct String from Binary Tree
- c#中不同类中变量的引用方法
- 学习css之选择器优先级
- Java学习之软件安装
- vue组件详解——组件通信
- checkbox的使用总结,判断是否选中
- 使用PHPExcel实现Excel文件的导入和导出(模板导出)
- tracert traceroute
- 利用 Express 托管静态文件
- @Scope注解设置创建bean的方式和生命周期
- HttpRequest中常见的四种Content-Type(转)