ToB企服应用市场:ToB评测及商务社交产业平台

标题: P1398 [NOI2013] 书法家 [打印本页]

作者: 金歌 时间: 2024-7-31 11:17
标题: P1398 [NOI2013] 书法家
思路：

来一篇极小常数的 \(O(N^3M)\) 和 \(O(N^2M \log^2 N)\) 的题解，最慢点在 500ms 以下但是为什么还是最劣解。
定义 \(dp_{i,j,k,x \in \{0,1,2\},y \in \{0,1,2\}}\) 表现对于正在画的第 \(x\) 个字符，现在正在画开头/中间/结尾，且当前画的矩形的右下角是 \((i,j)\) 和右上角 \((k,j)\)。
则状态转移方程为，为了使式子不外于太丑陋，分段函数就表现取 \(\max\)：

\[dp_{i,j,k,0,0} = \begin{cases} \sum\limits_{I=k}^i a_{I,j} \\ \sum\limits_{I=k}^i a_{I,j} + dp_{i,j-1,k} \end{cases}\]

\[dp_{i,j,k,0,1} = \sum\limits_{I=k}^i a_{I,j} + \begin{cases} \max\limits_{l=i+1}^n dp_{l,j-1,k,0,0} \\ \max\limits_{x=k}^i \max\limits_{y=1}^k dp_{x,j-1,y,0,1} \\ \max\limits_{y=1}^{k-1} dp_{k-1,j-1,y} \end{cases}\]

\[dp_{i,j,k,0,2} = \sum\limits_{I=k}^i a_{I,j} + \begin{cases} \max\limits_{l=k+1}^i dp_{i,j-1,l,0,1} \\ dp_{i,j-1,k,0,2} \end{cases}\]

\[dp_{i,j,k,1,0} = \sum\limits_{I=k}^i a_{I,j} + \max\limits_{x=1}^n \max\limits_{z=1}^{k-2} \max\limits_{y=1}^i dp_{i,z,y,0,2}\]

\[dp_{i,j,k,1,1} = a_{k,j} + a_{i,j} + \begin{cases} dp_{i,j-1,k,1,0} \\ dp_{i,j-1,k,1,1} \end{cases}\]

\[dp_{i,j,k,1,2} = \sum\limits_{I=k}^i a_{I,j} + dp_{i,j-1,k,1,1}\]

\[dp_{i,j,k,2,0} = a_{k,j} + a_{i,j} + \begin{cases} dp_{i,j-1,k,2,0} \\ \max\limits_{x=1}^n \max\limits_{z=1}^{k-2} \max\limits_{y=1}^i dp_{i,z,y,1,2} \end{cases}\]

\[dp_{i,j,k,2,1} = \sum\limits_{I=k}^i a_{I,j} + \begin{cases} dp_{i,j-1,k,2,0} \\ dp_{i,j-1,k,2,1}\end{cases}\]

\[dp_{i,j,k,2,2} = a_{k,j} + a_{i,j} + \begin{cases} dp_{i,j-1,k,2,1} \\ dp_{i,j-1,k,2,2} \end{cases}\]
对于一重循环部门，可以直接前缀/后缀预处置惩罚 \(\max\)；对于查询矩阵最大值部门，可以用二维 ST 表大概暴力扫一维然后预处置惩罚别的一维的前缀/后缀 \(\max\)。
时间复杂度为 \(O(N^3M)\) 或 \(O(N^2M \log^2 N)\)，由于感觉二维 ST 表可能快不了多少，于是没有写，有爱好的读者可以自己尝试一下。
空间可能开不下，要用滚动数组优化。
完整代码：

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef int ll;bool Begin;const ll N=155,M=505,INF=1e9; inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)