【题解】BZOJ P1057 dp

╰半夏微凉° 2023-08-17 16:49 84阅读 0赞

# 悬线法 #

部分内容参考Santiego的博客，侵删！侵删！侵删！

--------------------

### 0x00 关于悬线法 ###

只是因为这题用到了不然我干嘛写它

用于求满足某种状态的矩形，如最大01交替矩形

### 0x10 简单思想 ###

先预处理出ml\[i\]\[j\],mr\[i\]\[j\],mt\[i\]\[j\]

分别表示当前位置(i,j)能向左扩展到的最左边的编号、能向右扩展到最右边的编号、能向上扩展到最大高度

然后在dp时，除第一行，每行根据上一行的状态更新当前状态，逐行扫一遍

复杂度O(n\*m)

### 0x20 一些题 ###

[Luogu P2701 巨大的牛棚 Big Barn][Luogu P2701 _ Big Barn]

[Luogu P1169 棋盘制作][Luogu P1169]

[Luogu P4147 玉蟾宫][Luogu P4147]

### 0x30 题解（正文） ###

求01交替的最大矩形和正方形

那这道题就显然了

code

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 namespace gengyf{
     4 #define ll long long
     5     const int maxn=2005;
     6     inline int read(){
     7         int f=1,x=0;char s=getchar();
     8         while(!isdigit(s)){
         if(s=='-')f=-1;s=getchar();}
     9         while(isdigit(s)){x=x*10+s-'0';s=getchar();}
    10         return x*f;
    11     }
    12     int n,m,ml[maxn][maxn],mr[maxn][maxn],mt[maxn][maxn];
    13     int ans1,ans2,mp[maxn][maxn];
    14     void init(){
    15         for(int i=1;i<=n;i++)
    16             for(int j=2;j<=n;j++){
    17                 if(mp[i][j]!=mp[i][j-1])
    18                     ml[i][j]=min(ml[i][j-1],ml[i][j]);
    19             }
    20         for(int i=1;i<=n;i++)
    21             for(int j=m-1;j>=1;j--){
    22                 if(mp[i][j]!=mp[i][j+1])
    23                     mr[i][j]=max(mr[i][j+1],mr[i][j]);
    24             }
    25     }
    26     int main(){
    27         n=read();m=read();
    28         for(int i=1;i<=n;i++)
    29             for(int j=1;j<=m;j++){
    30                 mp[i][j]=read();
    31                 ml[i][j]=mr[i][j]=j;
    32                 mt[i][j]=1;
    33             }
    34         init();
    35         for(int i=1;i<=n;i++)
    36             for(int j=2;j<=m;j++){
    37                 if(i>1&&mp[i][j]!=mp[i-1][j]){
    38                     ml[i][j]=max(ml[i][j],ml[i-1][j]);
    39                     mr[i][j]=min(mr[i][j],mr[i-1][j]);
    40                     mt[i][j]=mt[i-1][j]+1;
    41                 }
    42                 int w=mr[i][j]-ml[i][j]+1;
    43                 int h=mt[i][j];
    44                 ans1=max(min(w,h)*min(w,h),ans1);
    45                 ans2=max(w*h,ans2);
    46             }
    47         printf("%d\n%d\n",ans1,ans2);
    48         return 0;
    49     }
    50 }
    51 signed main() {
    52     gengyf::main();
    53     return 0;
    54 }

Code

--------------------

所以，标签的单调栈在哪？？？

嗯，不知

![1658269-20190911171058976-1456401129.jpg][]

转载于:https://www.cnblogs.com/gengyf/p/11507380.html

[Luogu P2701 _ Big Barn]: https://luogu.org/problem/P2701
[Luogu P1169]: https://www.luogu.org/problem/P1169
[Luogu P4147]: https://www.luogu.org/problem/P4147
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230809/3a38db2987d6447aaf9dec42a8e1afae.png
[1658269-20190911171058976-1456401129.jpg]: /images/20230809/005f88fec68d40978cc911e81ab1f6c3.png