CF708D2

D题

题很好, 感觉思维得到了升华. 把整个题考虑成一个图, 对每对$\{i, j\}$, 只要tag[i] != tag[j]他们之间就要连边, 边权为$|2^i-2^j|$. 按照题意, 需要找一条边权不断上升的、$\sum|s_i-s_j|$最大的路. 由于边权不断上升, 可以将边按边权排序 (外层$i$从小到大, 内层$j$从大到小) , 然后使用动态规划: dp[i][t]维护只使用前$t$条边时, 终点为$i$的路的路径权值最大值. 考虑转移, 发现$t$增加$1$时只有至多两个dp值会发生变化, 因为一步只引入了一条边, 而且它只能被加在已经考虑过的路径的末尾. 这样, 我们可以舍弃$t$维度, 而代之以时间维度: $dp$数组只有一维, dp[i]维护当前时刻以$i$结尾的路的路径权值最大值. 每当时刻前进1, 就新考虑一条边, 更新一下dp[i]dp[j]: $dp_i = \max(dp_i, dp_j + |s_i - s_j|)$$dp_j=\max(dp_j, dp_i+|s_i-s_j|)$.