2020.7.18 牛客多校第三场

2020.7.20 牛客多校第四场

百度之星初赛第一场 rk:158 pros:5/5/8

CR655E

链接

tag：dp

题意：

一个$n \times m$的表格，每个行分为若干段（不重不漏、长度和数量无限制），每段可以选一个位置放1，其他位置放0，定义$f(i)$为第i列1的数量，求最大化的$\sum_{i=1}^m{f(i)}^2$

解法：观察性质：可以发现答案一定有一列是全1的（如果没有，则选一个1最多的列，将该列上非1格子全变成1，价值一定更大），由此可以构建dp状态dp[i][j]表示从第i行到第j列，只考虑包含在$[i,j]$中的段的最大价值，转移是枚举全放1的行（只考虑包含区间），即$dp_{i,j} = \max \limits_{i \leq k \leq j} {dp_{i,k-1}+dp_{k+1,j}+{g(k,i,j)}^2}$,其中g表示第k列中完全包含在i，j间的区间个数。时间复杂度：$O(n^4)$

comments：思路我做的时候完全没想到，全1列的性质在经过n小时冥思苦想后发现了，但是想不到可以对完全包含的区间来构建状态，思路很巧妙

没有专题

没有比赛

没有专题

没有比赛