关于状态设计的问题
查看原帖
关于状态设计的问题
832472
yishanyi楼主2024/12/15 09:47

蒟蒻以前一直觉得DPDP的状态设计因人而异，但解法是一样的，但这道题蒟蒻的O(n2)O(n^2)暴力DPDP的状态是dpi,jdp_{i,j}表示到第ii个数连续选了jj个数的最大和，转移有

dpi,j={dpi−1,j−1+ai, 1≤j≤min⁡(i,k)max⁡p=0min⁡(i,k)dpi−1,p, j=0dp_{i,j}= \begin{cases} dp_{i-1,j-1}+a_i,~1\le j \le \min(i, k)\\ \max_{p=0}^{\min(i,k)} dp_{i-1,p},~j=0 \end{cases}

然后发现这个转移好像不能单调队列优化

求巨佬喷解答

2024/12/15 09:47