ModestCoder_的博客

原题传送门决策单调性优化qwq决策单调性就是当前状态iii，两个决策j,k(j&lt;k)j,k(j&lt;k)j,k(j<k)，如果k更优，那么在i增大时，j永远不会逆袭这个时候满足决策单调性那么得到每个决策都对应一个区间使得这个决策对于区间里的状态是最优解好讲一下这道题目有点迷fi=max(aj+∣j−i∣)f_i=max(a_j+\sqrt{|j-i|})...

原题传送门令sumisum_isumi​表示第一个短语到第iii个短语组成的句子长度sumi=i−1+∑j=1istrlen(sj)sum_i=i-1+\sum_{j=1}^{i}strlen(s_j)sumi​=i−1+∑j=1i​strlen(sj​)轻松得到一个暴力dpdpdp:dpi=min(dpj+(sumi−sumj−L−1)P)dp_i=min(dp_j+(sum_i-sum_...