1398
myee
·
·
题解
Update
于 2024.1.11 修改了这篇题解的代码。
思路
什么毒瘤细节题。
考虑如何解决。
考虑对这些条件做出进一步的抽象。
于是我们做出细致的观察。
方便起见，我们横、纵坐标自左往右、自上往下标号。
字母之间的关系
O 的条件 2 与 I 的条件 2 指出，N，O 之间有至少一个空列，O，I 之间有至少一个空列，三个字母是依次排布的。
而且这些限制关系都是在横坐标上的，纵坐标上不做限制。
这启示我们只用算出前缀若干列的最优 N、中间若干列的最优 O、后缀若干列的最优 I，即可算出答案。
于是考虑对三者分别进行动态规划，最后合并答案。
（注意：事实证明这是一条错误的道路，但对后面的正解富有启发意义，且推导也是类似的）
方便起见，我们设 (c,r) 元素幸运值为 w(r,c)。
字母 N 的部分
先不管第一个、最后一个矩形，中间的矩形必然形如滑动窗口的形式，并且依次相接。
注意到拼接时，中间的矩形宽度（即横坐标跨度）若 >1，则可以拆成若干个宽度 =1 的矩形，则条件依旧成立。因此我们只用考虑中间矩形宽度均为 1 的情况。
然后考虑第一个矩形、最后一个矩形。我们不妨把他们也拆成上下端点保持不变的若干宽度为 1 的矩形。
我们称第一个矩形是第一类，中间的矩形是第二类，最后的矩形是第三类。
设计 dp 状态 f(col,l,r,op)，其中 col\in[1,m],1\le l\le r\le n,op\in\{1,2,3\}，表示当前考虑到第几列、目前矩形在当前列上上下端点、当前矩形种类都已确定的情况下，目前前缀矩形最大可行权。
考虑转移。
f(col,l,r,1)=\max\{f(col-1,l,r,1),0\}+\sum_{y=l}^rw(y,col)
f(col,l,r,2)=\max\{\max\{f(col-1,l,y,1)|y>r\},\max\{f(col-1,y_1,y_2,2)|y_1\le l,l-1\le y_2\le r\}\}+\sum_{y=l}^rw(y,col)
f(col,l,r,3)=\max\{\max\{f(col-1,y,r,2)|l<y\le r\},f(col-1,l,r,3)\}+\sum_{y=l}^rw(y,col)
然后直接做就好了。
这个东西可以通过简单的转移顺序与前后缀和做到复杂度与状态数同阶。
字母 I 的部分
对，先跳过 O。
主要是 O 的左右端点都要枚举，因此我们放在后面考虑。
I 是上下对齐的，考虑怎么做。
……
感觉好像不好做啊。
但是我们有 Q_1=H_1,Q_3=Q_3，即最上面、最下面的矩形高度都为 1。
我们试图重新考虑，把 I 视作一个整体，从右往左扫描。
我们发现，问题被分为三个“阶段”。
阶段 1：仅最上、最下格子被填充。
阶段 2：整段区间被填充。
阶段 3：仅最上、最下格子被填充。
设计 dp 状态 g(col,l,r,op)，表示当前考虑到第几列、I 的上下端点、当前阶段种类都已确定的情况下，目前后缀状态最大可行权。
考虑转移。
g(col,l,r,1)=\max\{g(col+1,l,r,1),0\}+w(l,col)+w(r,col)
g(col,l,r,2)=\max\{g(col+1,l,r,1),g(col+1,l,r,2)\}+\sum_{y=l}^rw(y,col)
g(col,l,r,3)=\max\{g(col+1,l,r,2),g(col+1,l,r,3)\}+w(l,col)+w(r,col)
然后直接做就好了。
字母 O 的部分
这个左右端点枚举似乎无法避免，考虑怎么优化。
似乎没法优化。
因为枚举端点已经带来了 \Theta(m^2) 级别的枚举了，无法承受甚至再来一个 n。
我们发现这个东西，如果硬枚举左右端点，然后按类似 I 的方式确定三个阶段 dp 的话，复杂度是 O(m^2n^2) 的。
换言之，我们的做法，在时间复杂度上假了！
重新合并三个字母 NOI
考虑挽救刚刚的做法。
不能分开处理，主要是因为 O 要枚举两个端点啊。
那么唯一的方法，就是联合处理了。
设 f(col,l,r,op) 定义同上，我们考虑如何继续维护 O。
设 h(col,l,r,op) 表示已经考虑了 N，当前考虑到第几列、O 的上下端点、当前阶段种类都已确定的情况下，目前前缀状态的最大可行权。
重新设 g(col,l,r,op) 表示已经考虑了 N 与 O，当前考虑到第几列、I 的上下端点、当前阶段种类都已确定的情况下，目前前缀状态最大可行权。
考虑转移。
我们列出如下 9 个转移方程。
f(col,l,r,1)=\max\{f(col-1,l,r,1),0\}+\sum_{y=l}^rw(y,col)
f(col,l,r,2)=\max\{\max\{f(col-1,l,y,1)|y>r\},\max\{f(col-1,y_1,y_2,2)|y_1\le l,l-1\le y_2\le r\}\}+\sum_{y=l}^rw(y,col)
f(col,l,r,3)=\max\{\max\{f(col-1,y,r,2)|l<y\le r\},f(col-1,l,r,3)\}+\sum_{y=l}^rw(y,col)
h(col,l,r,1)=\max\{f(c,y_1,y_2,3)|c\le col-2,y_1<y_2\}+\sum_{y=l}^rw(y,col)
h(col,l,r,2)=\max\{h(col-1,l,r,1),h(col-1,l,r,2)\}+w(l,col)+w(r,col)
h(col,l,r,3)=h(col-1,l,r,2)+\sum_{y=l}^rw(y,col)
g(col,l,r,1)=\max\{\max\{h(c,y_1,y_2,3)|c\le col-2,y_1<y_2\},g(col-1,l,r,1)\}+w(l,col)+w(r,col)
g(col,l,r,2)=\max\{g(col-1,l,r,1),g(col-1,l,r,2)\}+\sum_{y=l}^rw(y,col)
g(col,l,r,3)=\max\{g(col-1,l,r,2),g(col-1,l,r,3)\}+w(l,col)+w(r,col)
然后最大的 g(col,l,r,3) 就是答案。
如何 O(1) 转移
状态数是 \Theta(n^2m) 的，我们需要的复杂度也只能是这个级别，但并不方便直接解决这一点。
显然，这个东西的转移如何做到 O(1) 并不是显然的。
我们先确认以下事实：\max 旁边所加的项均为 \sum_{y=l}^rw(y,col) 或 w(l,col)+w(r,col)。
于是设 A(col,l,r)=\sum_{y=l}^rw(y,col),B(col,l,r)=w(l,col)+w(r,col)。
而之前的 dp 状态，其拓扑序显然。
接下来，我们依次处理每部分如何做到 $O(1)$ 转移。
---
$$f(col,l,r,1)=\max\{f(col-1,l,r,1),0\}+A(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$f(col,l,r,2)=\max\{\max\{f(col-1,l,y,1)|y>r\},\max\{f(col-1,y_1,y_2,2)|y_1\le l,l-1\le y_2\le r\}\}+A(col,l,r)$$
设 $p(col,l,r)=\max\{f(col,l,y,1)|y>r\}$，则 $p(col,l,r)=\max\{p(col,l,r+1),f(col,l,r+1,1)\}$，边界稍微特判一下。
则
$$f(col,l,r,2)=\max\{p(col-1,l,r),\max\{f(col-1,y_1,y_2,2)|y_1\le l,l-1\le y_2\le r\}\}+A(col,l,r)$$
设 $q(col,l,r)=\max\{f(col,y_1,y_2,2)|y_1\le l,l-1\le y_2\le r\}$。
则 $q(col,l,r)=\max\{\max\{f(col,y,r,2)|y\le l\},q(col,l,r-1)\}$，边界要特殊处理。
设 $d(col,l,r)=\max\{f(col,y,r,2)|y\le l\}$。
则 $d(col,l,r)=\max\{f(col,l,r,2),d(col,l-1,r)\}$，边界要特殊处理。
则 $q(col,l,r)=\max\{d(col,l,r),q(col,l,r-1)\}$。
则
$$f(col,l,r,2)=\max\{p(col-1,l,r),q(col-1,l,r)\}+A(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$f(col,l,r,3)=\max\{\max\{f(col-1,y,r,2)|l<y\le r\},f(col-1,l,r,3)\}+A(col,l,r)$$
设 $p(col,l,r)=\max\{f(col,y,r,2)|l<y\le r\}$。
则 $p(col,l,r)=\max\{f(col,l+1,r,2),p(col,l+1,r)\}$，边界要特殊处理。
$$f(col,l,r,3)=\max\{p(col-1,l,r),f(col-1,l,r,3)\}+A(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$h(col,l,r,1)=\max\{f(c,y_1,y_2,3)|c\le col-2,y_1<y_2\}+A(col,l,r)$$
设 $p(col)=\max\{f(c,y_1,y_2,3)|c<col,y_1<y_2\}$。
则 $p(col)=\max\{p(col-1),\max\{f(col-1,y_1,y_2,3)|y_1<y_2\}\}$，这个直接暴力合并即可。
$$h(col,l,r,1)=p(col-1)+A(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$h(col,l,r,2)=\max\{h(col-1,l,r,1),h(col-1,l,r,2)\}+B(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$h(col,l,r,3)=h(col-1,l,r,2)+A(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$g(col,l,r,1)=\max\{\max\{h(c,y_1,y_2,3)|c\le col-2,y_1<y_2\},g(col-1,l,r,1)\}+B(col,l,r)$$
设 $p(col)=\max\{h(c,y_1,y_2,3)|c<col,y_1<y_2\}$。
则 $p(col)=\max\{p(col-1),\max\{h(col-1,y_1,y_2,3)|y_1<y_2\}\}$，这个直接暴力合并即可。
$$g(col,l,r,1)=\max\{p(col-1),g(col-1,l,r,1)\}+B(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$g(col,l,r,2)=\max\{g(col-1,l,r,1),g(col-1,l,r,2)\}+A(col,l,r)$$
直接按 $col$ 升序转移即可。
---
$$g(col,l,r,3)=\max\{g(col-1,l,r,2),g(col-1,l,r,3)\}+B(col,l,r)$$
直接按 $col$ 升序转移即可。
---
### Code
按刚刚说的，硬写，然后就完了。
NOI2013D2T2 果然是绝世\*\*题。
然后这题还卡空间，记得滚动数组。
以下是核心代码。
```cpp
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
T ans=1%mod;
while(index)
{
if(index&1)ans=ans*base%mod;
base=base*base%mod,index>>=1;
}
return ans;
}
const int inf=1e8;
int W[155][505],A[155][155],B[155][155],F[155][155][4],G[155][155][4],H[155][155][4];
voi solve()
{
uint n,m;scanf("%u%u",&n,&m);
for(uint i=1;i<=n;i++)for(uint j=1;j<=m;j++)scanf("%d",W[i]+j);
for(uint i=0;i<=n+1;i++)for(uint j=0;j<=n+1;j++)for(uint op=1;op<=3;op++)F[i][j][op]=-inf;
for(uint i=0;i<=n+1;i++)for(uint j=0;j<=n+1;j++)for(uint op=1;op<=3;op++)H[i][j][op]=-inf;
for(uint i=0;i<=n+1;i++)for(uint j=0;j<=n+1;j++)for(uint op=1;op<=3;op++)G[i][j][op]=-inf;
int ans=-inf;
for(uint col=1;col<=m;col++){
static int NO=-inf,OI=-inf,User[155][155];
#define W(c,r) W[r][c]
#define A(l,r) A[l][r]
#define B(l,r) B[l][r]
#define F(l,r,op) F[l][r][op]
#define H(l,r,op) H[l][r][op]
#define G(l,r,op) G[l][r][op]
#define p(l,r) User[l][r]
for(uint l=1;l<=n;l++)for(uint r=l;r<=n;r++)A(l,r)=A(l,r-1)+W(col,r),B(l,r)=W(col,l)+W(col,r);
for(uint l=1;l<=n;l++)for(uint r=l+2;r<=n;r++)_max(G(l,r,3),G(l,r,2)),_max(ans,G(l,r,3)+=B(l,r));
for(uint l=1;l<=n;l++)for(uint r=l+2;r<=n;r++)_max(G(l,r,2),G(l,r,1)),G(l,r,2)+=A(l,r);
for(uint l=1;l<=n;l++)for(uint r=l+2;r<=n;r++)_max(G(l,r,1),OI),G(l,r,1)+=B(l,r);
for(uint l=1;l<=n;l++)for(uint r=l+2;r<=n;r++)_max(OI,H(l,r,3)),H(l,r,3)=H(l,r,2)+A(l,r);
for(uint l=1;l<=n;l++)for(uint r=l+2;r<=n;r++)_max(H(l,r,2),H(l,r,1)),H(l,r,2)+=B(l,r);
for(uint l=1;l<=n;l++)for(uint r=l+2;r<=n;r++)H(l,r,1)=NO+A(l,r);
for(uint l=1;l<=n;l++)for(uint r=l+1;r<=n;r++)_max(NO,F(l,r,3));
for(uint l=0;l<=n+1;l++)for(uint r=0;r<=n+1;r++)p(l,r)=-inf;
for(uint l=n;l;l--)for(uint r=l+1;r<=n;r++)p(l,r)=std::max(p(l+1,r),F(l+1,r,2));
for(uint l=1;l<=n;l++)for(uint r=l+1;r<=n;r++)_max(F(l,r,3),p(l,r)),F(l,r,3)+=A(l,r);
for(uint l=0;l<=n+1;l++)for(uint r=0;r<=n+1;r++)p(l,r)=-inf;
for(uint l=1;l<=n;l++)for(uint r=l-1;r<=n;r++)p(l,r)=std::max(p(l-1,r),F(l,r,2));
for(uint l=1;l<=n;l++)for(uint r=l;r<=n;r++)_max(p(l,r),p(l,r-1));
for(uint l=1;l<=n;l++)for(uint r=l;r<=n;r++)F(l,r,2)=p(l,r);
for(uint l=0;l<=n+1;l++)for(uint r=0;r<=n+1;r++)p(l,r)=-inf;
for(uint l=1;l<=n;l++)for(uint r=n;r>=l;r--)p(l,r)=std::max(p(l,r+1),F(l,r+1,1));
for(uint l=1;l<=n;l++)for(uint r=l;r<=n;r++)_max(F(l,r,2),p(l,r)),F(l,r,2)+=A(l,r);
for(uint l=1;l<=n;l++)for(uint r=l+1;r<=n;r++)_max(F(l,r,1),0),F(l,r,1)+=A(l,r);
#undef p
#undef G
#undef H
#undef F
#undef B
#undef A
#undef W
}
printf("%d\n",ans);
}
```