这题.. 我真傻, 真的.. 我单知道单调队列可以优化 dp, 加上平衡树, 却不知道单调栈就可以..
所以说常见模型要记住啊!!!
求给定矩形最大的同字母矩形面积.(字母数: a,b,c) 多组数据 $n,m≤1000$
真的学傻掉了.. 写出来一个 $O(n^3)$dp 方程还跟真的一样去想优化.. 最后只能做到 $O(n^2logn)$..
一开始大体就是对于每行的每个字母, 都可以统计出前 i 行这一列到他最长维持多少个相同字母. 这就是像是个直方图, 然后去找最大面积即可.
$S_max = max{min(a[i]~a[j])*(j-i+1)}$
这个并不需要 dp. 观察一下, 这不就是上天那个和良好的感觉差不多的题吗? 枚举每个点, 拓展两边直到找到比他小 (矮) 的, 算下面积.
我还是太菜了啊.
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<cmath>
- #include<queue>
- using namespace std;
- typedef long long ll;
- template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
- template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
- template<typename T>inline T _min(T A,T B){return A<B?A:B;}
- template<typename T>inline T _max(T A,T B){return A>B?A:B;}
- template<typename T>inline T read(T&x){
- x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
- while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
- }
- const int N=1000+7;
- char s[N];
- int h[N][3],q[N],f[N];
- int n,m,l,r,ans;
- inline void get_h(int j){
- switch(s[j]){
- case 'a':++h[j][0],h[j][1]=h[j][2]=0;break;
- case 'b':++h[j][1],h[j][0]=h[j][2]=0;break;
- case 'c':++h[j][2],h[j][0]=h[j][1]=0;break;
- case 'w':++h[j][0],++h[j][1],h[j][2]=0;break;
- case 'x':++h[j][1],++h[j][2],h[j][0]=0;break;
- case 'y':++h[j][0],++h[j][2],h[j][1]=0;break;
- case 'z':++h[j][0],++h[j][1],++h[j][2];break;
- }
- }
- inline void dp(int p){
- l=1,q[r=0]=0;// 注意更新 q[0]!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
- for(register int i=1;i<=m;++i){
- while(l<=r&&h[q[r]][p]>=h[i][p])--r;
- f[i]=q[r]+1,q[++r]=i;
- }
- l=1,q[r=0]=m+1;// 注意更新
- for(register int i=m;i;--i){
- while(l<=r&&h[q[r]][p]>=h[i][p])--r;
- MAX(ans,(q[r]-f[i])*h[i][p]),q[++r]=i;
- }
- }
- int main(){//freopen("test.in","r",stdin);//freopen("tmp.out","w",stdout);
- while(~scanf("%d%d",&n,&m)){
- ans=0;memset(h,0,sizeof h);
- for(register int i=1;i<=n;++i){
- scanf("%s",s+1);
- for(register int j=1;j<=m;++j)get_h(j);
- dp(0),dp(1),dp(2);
- }
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2971639.html