[CF 273D]Dima and Figure解题报告

题目翻译


题解

就是DP……
F[k][mask][i][j]代表:当前图形的最下端是第k行,左右边界的开放/收缩情况是mask,第k行涂黑了i~j列。
具体讲,mask=0代表左右边界均收缩,mask=1代表左开放右收缩,mask=2代表左收缩右开放,mask=3代表左右均开放。
“收缩”左边界的意思是:在第k行之前的每一行,涂黑部分最左都没有越过i,右边界就是最右没有越过j。
“开放”左边界的意思是:在第k行之前的某一行,涂黑部分最左越过了i,右边界就是某一行越过了j。
显然,收缩边界只能由收缩边界转移而来,否则就不满足那个曼哈顿距离的条件了。更准确地说,左右边界都是①一直开放,②一直收缩,③先一直收缩再一直开放(纺锤形)三种情况之一。
裸这样做复杂度太高,可以给F数组记一个前缀和S,用前缀和快速求区间和。
同时,F和S数组可以互相滚动(这样就去掉了k那一维),非常方便。
转移……就是各种分类讨论吧,详见代码

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注