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